zhangas

Pay more attention

0%

Veröffentlicht am

P7714 「EZEC-10」排列排序

题目链接
双指针求小区间的长度之和[L,R]满足R大于等于区间内最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[1000005];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    int ma=0;//区间内最大值
    int ans=0;
    for(int l=1,r=1;r<=n;r++){
        ma=max(ma,a[r]);
        while(l<r&&a[l]==l){
            l++;
        }
        if(r==ma&&l<r){
            ans+=r-l+1;
            l=r+1;
            ma=0;
        }
    }
    cout<<ans<<endl;
}

P3611 [USACO17JAN] Cow Dance Show S

题目链接
N个牛 第i头牛跳舞花费a_i 最大时间为T 求不超过时间T的前提下
最少多少个舞台够使用
二分check 答案区间[1,n]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool check(int mid){
    //每次取最小的时间叠加 检验最大的时间是否大于t
    priority_queue<int,vector<int>,greater<int>>heap;
    for(int i=1;i<=mid;i++){
		heap.push(a[i]);
	}
	for(int i=mid+1;i<=n;i++){
		int t=hash.top();
		heap.pop();
		heap.push(t+a[i]);
	}
	while(heap.size()>1){
		heap.pop();
	}
	if(heap.top()>s)return false;
	return true;
}
int main(){
    sort(a+1,a+1+n);
    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
}

P1572 计算分数

题目链接
读入字符串后 分解成n个分数
f[i]的1和-1表示符号 a[i]表示分子 b[i]表示分母
通分为Π[i] 分子带入计算
分子和分母同时除以__gcd(a,b)
b为1的时候 不输出分号和b

Veröffentlicht am Bearbeitet am

P3029 [USACO11NOV] Cow Lineup S

题目链接
求包含K种数字的最短连续子序列长度
双指针 维护连续子序列[L,R]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct node{
    int x,id;
};
node a[50005];
int n,k;
unordered_map<int,int>mp;
bool cmp(node xx,node yy){
    return xx.x<yy.x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i].x=read(),a[i].id=read();
        if(!mp[a[i].id]){
            k++;
            mp[a[i].id]=1;
        }
    }
    mp.clear();
    sort(a+1,a+1+n,cmp);
    int ans=1e9;
    int cnt=0;
    for(int l=1,r=1;r<=n;r++){
        if(!mp[a[r].id]){
            cnt++;
        }
        mp[a[r].id]++;
        while(l<r&&mp[a[l].id]>1){
            l++;
            mp[a[l].id]--;
        }
        if(cnt==k)ans=min(ans,a[r].x-a[l].x);
    }
    cout<<ans;
}

P3029 P1934 封印

题目链接
1.dp[i]由上一层加上a[i]*N^2递推
2.dp[i]由前面第j层加上(a[j]+a[j+1]+…+a[i])x(a[j]+a[i])递推 需要满足a[i]+a[j]<=t这一条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n,t;
int a[1005],b[1005],dp[1005];
int main(){
    n=read(),t=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=b[i-1]+a[i];//a[i]的前缀和 用于O(1)求数组a的区间和
    }
    int m=n*n;
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        dp[i]=min(dp[i],dp[i-1]+a[i]*m);
        for(int j=1;j<i;j++){
            if(a[i]+a[j]<=t){
                dp[i]=min(dp[i],dp[j-1]+(b[i]-b[j-1])*(a[i]+a[j]));
            }
        }
    }
    cout<<dp[n];
}

Veröffentlicht am

P1210 [USACO1.3] 最长的回文 Calf Flac

题目链接
包含标点符号、空格的字符串，再只考虑字母的条件下求最长回文串
转化为只含有小写字母的字符串，利用map映射俩字符串的坐标，再进行操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//坐标映射 只需要处理数组d
for(int i=1;i<=n;i++){
	if(isalpha(c[i])){
		d[++m]=tolower(c[i]);
		mp[m]=i;
	}
}
//遍历一遍点 然后向两端扩展
int l,r;
void check(int e){
    int a=1;
    for(int i=1;d[e-j]==d[e+j];i++){
        if(e-j<1)break;
        if(e+j>m)break;
        a+=2;
    }
    int b=0;
    for(int i=1;d[e-j]==d[e+j+1];i++){
        if(e-j<1)break;
        if(e+j+1>m)break;
        b+=2;
    }
    int t=max(a,b);
    if(t>ans){
        ans=t;
        l=e-ans/2;
        if(ans%2==0)l++;//!!如果字符串的长度是偶数 除以2之后应该加上1  #3 WA
        r=e+ans/2;
    }
}

Veröffentlicht am

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int e[N],ne[N],h[N],w[N],idx;
void add(int a,int b,int c){
    e[idx]=b;//e[]数组存数边的终点
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;//记录以t为出发点对应的第几条边
}

int main(){
    memset(h,-1,sizeof(h));
    //遍历以t为出发点的所有线路
    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];//t->j
        if(dist[j]>dist[t]+w[i]){
            dist[j]>dist[t]+w[i]
            ...
        }
    }
}

vector存图

1
2
3
4
5
6
7
8
9
vector<int>g[N];
for(int i=1;i<=m;i++){
    int a=read(),b=read();
    g[a].push_back(b);
}
//遍历
for(auto &i:g[t]){
    //t->i//这条边
}

Veröffentlicht am

P3906 Geodetic集合

题目链接
无向图边长度为1 Q次询问求两点u，v之间最短距离经过的点集
N<=40 floyed处理多源最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i!=j)g[i][j]=1e9;
        else g[i][j]=0;
    }
}
floyed();
//枚举询问a和b之间的点i 满足g[a][i]+g[i][b]
while(q--){
    int a=read(),b=read();
    vector<int>v;
    v.push_back(a),v.push_back(b);
    for(int i=1;i<=n;i++){
        if(i!=a&&i!=b){
            if(g[a][i]+g[i][b]==g[a][b]){
                v.push_back(i);
            }
        }
    }
    sort(v.begin(),v.end());
    for(auto &i:v)cout<<i<<' ';
    puts("");

}

P2850 [USACO06DEC] Wormholes G

题目链接
m条路线(无向边) 从u到v花费时间p
w个虫洞(有向边) 从u到v可以回到时间p之前
判断是否可以回到出发点同时也是出发时刻以前的某一时刻
spfa判断是否存在负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int idx,e[2505],ne[2505],h[2505],w[2505];
int cnt[405];
int st[405];
int dist[405];
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
bool spfa(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=1;//加入集合
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            //t->j
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)return true;
                if(!st[j]){
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
    return false;
}
void solve(){
    memset(h,-1,sizeof(h));
	memset(e,0,sizeof(e));
	memset(ne,0,sizeof(ne));
	memset(w,0,sizeof(w));
	memset(cnt,0,sizeof(cnt));
	memset(st,0,sizeof(st));
    idx=0;
    while(m--){
		int a=read(),b=read(),c=read();
		add(a,b,c),add(b,a,c);
	}
	while(p--){
		int a=read(),b=read(),c=read();
		add(a,b,-c);
	}
}

P8893 「UOI-R1」智能推荐

题目链接
从第0天开始 每一天你可以做以前推荐过的或者当天推荐的题
但有r个规则 在做第i道前要完成s道题目
求出做出第K道题需要的天数 如果不可以输出-1

从所有入度为0的点出发 跑一遍最短路dist[k]==0x3f3f3f3f时不能实现
注意N<=500但是有T组数据 T<=5 不可以Floyed求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
vector<int>a[505];//存图
void spfa(){
    while(q.size()){
        int t=q.front();
        q.pop();
        for(auto &i:a[t]){
			ru[i]--;
			if(!ru[i]){
				dist[i]=min(dist[i],dist[t]+1);
				q.push(i);
			}
		}
    }
    if(dist[k]==0x3f3f3f3f)cout<<"-1";
    else cout<<dist[k];
}
memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=p;i++){
    int t=read();
    dist[t]=0;//出发点处理
    q.push(t);
}
int r=read();
for(int i=1;i<=r;i++){
    int v=read(),s=read();
    while(s--){
        int t=read();
        //t->v有向边
        a[t].push_back(v);
        ru[v]++;
    }
}
spfa();

P4826 [USACO15FEB] Superbull S

题目链接
给N个数 以任意两个数的异或为边长建图 求其最大生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int f[2005];
int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
struct Edge{
    int a,b,c;
}edges[4000005];//边为(N+1)*n/2条
bool cmp(Edge x,Edge y){
    return x.c>y.c;
}
int a[2005];
int n=read();
for(int i=1;i<=n;i++){
    f[i]=i;
}
int m=0;
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        edges[m++]={i,j,a[i]^a[j]};
    }
}
sort(edges,edges+m,cmp);
int ans=0;
for(int i=0;i<m;i++){
    int x=edges[i].a,y=edges[i].b,w=edges[i].c;
    x=find(x),y=find(y);
    if(x!=y){
        f[x]=y;
        ans+=w;
        cnt++;
    }
    if(cnt==n-1)break;
}
cout<<ans;

P1744 采购特价商品

题目链接
给出N个点坐标和M对点之间有通路 且以两点之间的距离作为边权 求第S个点到第T个点的最短距离
N<=100 floyed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int x[105],y[105];
double g[105][105];
void floyed(){
    ...
}
int n=read();
for(int i=1;i<=n;i++){
    x[i]=read(),y[i]=read();
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i!=j)g[i][j]=1e9;
    }
}
int m=read();
while(m--){
    int a=read(),b=read();
    int xx=x[a]-x[b],yy=y[a]-y[b];
    dist[a][b]=min(dist[a][b],sqrt(xx*xx+yy*yy));
    dist[b][a]=min(dist[b][a],sqrt(xx*xx+yy*yy));
}
floyed();
int s=read(),t=read();
cout<<dist[s][t];

P2700 逐个击破

题目链接
N个城市由N-1条线路相连 其中K个是红点(不能在同一个连通块内)
给出N-1条可删去的线路和代价 求最小代价
最小代价==所有代价之和-尽可能多连接的线路之和
连通块维护 查询 vis[]数组标记是否产生冲突

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
bool cmp(Edge x,Edge y){
    return x.c>y.c;
}
struct Edge{
    int a,b,c;
}edges[100005];
int n=read(),k=read();
for(int i=0;i<k;i++){
    int t=read();
    vis[t]=1;
}
int sum=0;
for(int i=1;i<=n;i++){
    f[i]=i;
}
for(int i=0;i<n-1;i++){
    int a=read(),b=read(),c=read();
    sum+=t;
    edges[i]={a,b,c};
}
sort(edges,edges+n-1,cmp);
int res=0;
for(int i=0;i<n-1;i++){
    int x=edges[i].a,y=edges[i].b,w=edges[i].c;
    x=find(x),y=find(y);
    if(vis[x]==0||vis[y]==0){//两个点至少有一个不是敌人
        f[x]=y;
        res+=w;
        if(vis[x])vis[y]=1;
        if(vis[y])vis[x]=1;//同一连通块内不能连接两个敌人
    }
}
cout<<sum-res;

Veröffentlicht am

P1506 拯救oibh总部

题目链接
0是土地 *是墙 洪水从四面八方过来 求未被淹没的土地数量
扫一下边缘一圈，为0可以dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char c[505][505];
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
void dfs(int x,int y){
    if(c[x][y]=='*')return;
    c[x][y]='-';
    for(int i=1;i<=4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
            dfs(xx,yy);
        }
    }
}
int n,m;
int ans;
for(int i=1;i<=n;i++)dfs(i,1),dfs(i,m);
for(int i=1;i<=m;i++)dfs(1,i),dfs(n,i);
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        ans+=c[i][j]=='0'?1:0;
    }
}

B3626 跳跃机器人

题目链接
dp[i]=min(dp[i],dp[i-1]+1);
如果未到右边界才可由dp[i+1]+1转移
为偶数可由dp[i/2]+1转移
奇数可由dp[(i-1)/2]+2转移
如果未到右边界才可由dp[(i+1)/2]+2转移

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[1000005];
for(int i=2;i<=n+1;i++)dp[i]=n;//一定要初始化到N+1 考虑边界的情况
dp[1]=0;
for(int i=2;i<=n;i++){
    dp[i]=min(dp[i],dp[i-1]+1);
    if(i!=n)dp[i]=min(dp[i],dp[i+1]+1);
    if(i%2==0)dp[i]=min(dp[i],dp[i/2]+1);
    else{
        dp[i]=min(dp[i],dp[(i-1)/2]+1);
        if(i!=n)dp[i]=min(dp[i],dp[(i+1)/2]+1);
    }
}
cout<<dp[n];

P2037 电话号码

题目链接
STL模拟问题 set去重+排序 unordered_map映射个数
N<=100000 且 电话号码长度不会超过1000
O(N)*(1000)==1e9可过

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(string s){
    for(int i=0;i<s.szie();i++){
        if(s[i]>='A'&&s[i]<='Z')s[i]=...;
    }
    //处理-
    string ss='';
    for(auto i:s){
        ss+=i;
        if(ss.size()==3)ss+='-';
    }
    set.insert(ss);
    mp[ss]++;
}

P6183 [USACO10MAR] The Rock Game S

题目链接
将状态作为N位二进制表示0就是O 1就是X
求出一种方案使得相邻两种状态恰好有一位不同且无重复状态出现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int vis[1<<15+5];
bool dfs(int e){
    if(!vis[e]){
        //输出e的状态:从左到右输出二进制表示
        //与运算 两者都为1 才为1 否则为0
        for(int i=n-1;i>=0;i++){
            int t=e&(1<<i);
            if(t)cout<<'X';
            else cout<<'O';
        }
        vis[e]=1;
        //取^任意改变一位
        //异或运算 不同为1 相同为0
        for(int i=0;i<=n-1;i++){
            if(dfs(x^(1<<i)))
                return true;
        }
        return true;
    }
    return false;
}
dfs(0);

Veröffentlicht am

P2362 围栏木桩

题目链接
T次询问 求序列最长上升子序列长度和个数 N^2可过
f[i]记录以a[i]结尾的序列长度
s[i]记录以a[i]结尾的序列个数
f[j]>=f[i]时 取最大个数 s[i]=s[j]
f[j]< f[i] 且 f[j]+1==f[i]时 加上a[i]使得序列长度相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=n;i++){
    f[i]=s[i]=1;
    for(int j=1;j<i;j++){
        if(a[j]<=a[i]){//单调不减序列
            if(f[j]>=f[i]){
                f[i]=f[j]+1;
                s[i]=s[j];
            }
            else if(f[j]+1==f[i]){
                f[i]+=f[j];
            }
        }
    }
}

P2390 地标访问

题目链接
预处理出0到位置p的地标个数
四种情况1左 2右 3先左然后拐右 4先右然后拐右左
1 2 O(1)可以得到
3 4可以筛一遍地标 O(N) 注意t可能超过整个来回的可能 我就是错这里 就30pts了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int a[100005],b[100005];//预处理坐标P到原点之间的地标个数
int aa[50005],bb[50005];//存储地标
int l,r;
int lm,rm;//两端最远距离
int lc,rc;//两端地标个数
    int ans=0;
    //1 2两种情况
	if(t>=lm)
		ans=max(ans,lc);
	else
		ans=max(ans,a[t]);
	if(t>=rm)
		ans=max(ans,rc);
	else
		ans=max(ans,b[t]);
    //3 4两种情况
    for(int i=1;i<=lc;i++){
		if(t>aa[i]*2){//足够一个来回才有意义更新答案
			int g=t-aa[i]*2;
			int res=a[aa[i]];
			if(g>=rm)res+=rc;//如果返回后也超过另一方向
			else res+=b[g];	
			ans=max(ans,res);
		}
		
	}
	for(int i=1;i<=rc;i++){
		if(t>bb[i]*2){
			int g=t-bb[i]*2;
			int res=b[bb[i]];
			if(g>=lm)res+=lc;
			else res+=a[g];
			ans=max(ans,res);
		}
	}

P1388 算式

题目链接
2≤ n ≤ 15,0 ≤ k< n

预处理出区间和再 对K个乘法的位置爆搜81pts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n,m;
int a[50];
int b[50];//a数组的前缀和
int vis[50];
int ans;
//put * in position e
void dfs(int e,int d,int sum){//e是位置 d是深度 sum是局部答案
	if(d==m){
		ans=max(ans,sum*(b[n]-b[e]));
		return;
	}
	for(int i=e+1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			dfs(i,d+1,sum*(b[i]-b[e]));
			vis[i]=0;
		}
	}
}
dfs(0,0,1);//是k+1个数的乘积 所以sum初始化为1

P1676 [USACO05FEB] Aggressive cows G

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sort(a+1,a+1+n);
int r=a[n]-a[1];//最大距离
int l=r;
for(int i=1;i<n;i++){
	l=min(l,a[i+1]-a[i]);//最小距离
}
//答案就在[L,R]中
while(l<r){
    int mid=(l+r+1)>>1;
    if(check(mid)){
        l=mid;
    }
    else r=mid-1;
}

check函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool check(int e){
    //检查满足最小距离为e的情况下 是否可以放置m个奶牛
    //有个贪心思想 如果从最右边的牛舍开始放都不能满足条件 那么从右侧某个牛舍开始也一定不能满足条件
    int cnt=1,res=a[1];
    for(int i=2;i<=n;i++){
        int t=a[i]-res;
        if(t>=e){
            cnt++;
            res=a[i];
        }
    }
    if(cnt>=m)return true;
    return false;
}

Veröffentlicht am

P1114 “非常男女”计划

题目链接

N^2暴力 60pts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   int n=read();
for(int i=1;i<=n;i++){
	t[i]=read();
	if(t[i])a[i]=1;
	else b[i]=1;
}
for(int i=1;i<=n;i++){
	a[i]+=a[i-1];
	b[i]+=b[i-1];
}
int ans=0;
for(int i=1;i<=n;i++){
	for(int j=i+1;j<=n;j++){
		int aa=a[j]-a[i-1];
		int bb=b[j]-b[i-1];
		if(aa==bb)
			ans=max(ans,j-i+1);
	}
}
cout<<ans<<endl;

借助局部答案优化内层循环 100pts 不是正解,数据大仍可hack

1
2
3
4
5
6
7
8
   for(int i=1;i<=n;i++){
    int k=max(1,ans);
    for(int j=i+k;j<=n;j++){
		int aa=a[j]-a[i-1];
		int bb=b[j]-b[i-1];
			ans=max(ans,j-i+1);
	}
}

正解： 边读入边处理 分两种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unordered_map<int,int>mp;
int n=read();
int ans=0;
for(int i=1;i<=n;i++){
	t[i]=read();
	if(!t[i])
           t[i]=-1;//女生标注为-1
	t[i]+=t[i-1];
	if(!t[i])//当人数相等时 即和为0
		ans=i;
	else{//有-1 和 1两种可能
		if(mp[t[i]]){//减去第一次出现-1 或者1 的下标
			ans=max(ans,i-mp[t[i]]);
		}
		else mp[t[i]]=i;
	}
}
cout<<ans;

P3074 [USACO13FEB] Milk Scheduling S

题目链接
有M个要求：奶牛A必须在奶牛B前挤奶
为了尽量完成挤奶任务，聘请了一大批雇工协助任务，同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请计算挤奶过程中的最小总时间。

找出所有非孤立且入度为0的点dfs即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[10005];
int ru[10005];
vector<int>d[10005];
int ans;
int t[10005];
int dfs(int u){
	if(t[u]!=0)//记忆化搜索
		return t[u];
	int res=0;
	for(int i=0;i<d[u].size();i++){
		int v=d[u][i];
		//u -> v
		res=max(res,dfs(v));
	}
	return t[u]=res+a[u];
}

1<=N<=10,000 1<=M<=50,000 借助稀疏图存储路径
显然孤立点消耗的时间就是读入的时间，应该在所有孤立点中取最长时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   for(int i=1;i<=n;i++){
	a[i]=read();
}
   while(m--){
       //a -> b
	int a=read(),b=read();
	ru[b]++;
	d[a].push_back(b);//建图
}
   for(int i=1;i<=n;i++){
       if(d[i].size()==0)
           t[i]=a[i];
   }
   for(int i=1;i<=n;i++){
	if(ru[i]==0&&d[i].size()>0){
		dfs(i);
	}
}
   for(int i=1;i<=n;i++){
       ans=max(ans,t[i]);
   }
   cout<<ans<<endl;

Veröffentlicht am 
22年填报志愿时，是50190位次，本来也不够数学的位次，应该录取我的是50225的通信工程，
但是有了吴方班的出现使得普通班降了4000的位次。我很幸运遇到了一位21届从数学转出的学长，
使得从我入学的几天起我就暗暗下定决心转专业。今日写下这个建议，希望可以延续有想法的学弟学妹。

总结来说就是: 运气+绩点硬实力+c语言绝对水平

转专业文件分析

（1）高考综合改革省份学生须选考物理。其他省份考生须为理工类考生。
高考成绩在折算为 750 分后，须不低于该专业在山东省 2022年最低录取分数下 20 分。
考生需提供相应证明材料。

这个是硬要求，不满足直接就不能申请，因为面试前老师会让你打印当年的成绩查询成绩单。

（2）一年级考生申请转入我院各专业的，第一学期所学必修课程考试全部合格，无补考、重修记录，
且总成绩在原专业年级排名在 20%（含）以内（以报名时在教务系统中的排名为准）。

文件绩点要求只看大一上排名+大一下不挂科这一要求，原专业位次最好5%上下 低于10%有些危险(面试会看这个)；
学长当年是加权3.88 位次7.4% 也算是勉勉强强合格。

机考分析

申请转入我院的考生，须参加 C 语言机试，机试平台为我校 OJ平台，OJ 平台网址及机考要求在考试前公布。
该课程可通过我校网络教学平台上的《程序设计基础》慕课课程*进行自学，参考教材为《从问题到程序：程序
设计与 C 语言引论》（第 2 版）（裘宗燕，机械工业出版社，2011 年出版）。

机考的难度比外院的c语言期末高很多，但近似于计算机学院的c语言期末考试难度
建议多做OJ 上的题目，老实对待c语言课程，差不多可以30分钟做完外院的期末考试水平就够了。
最稳妥的是在机考2h内将所有题目做完 最多剩一道

面试分析

根据报名人数分为若干个面试小组，每个小组由 3—5 名教师组成。
面试满分为 100 分。面试成绩是面试小组各位专家评分的平均分。

注意: 面试的问题很基础，不会涉及专业课知识，只是简单问问你对本专业的认知和学习生活习惯,但是要老老实实准备，面试也会筛选人数。
牢记 计算机科学与工程学院——计算机科学与技术 提问的时候可能会要求辨析

运气

从21届降转的取消，再到22届分数线要求和18进6这一比例，这条道路的难度一目了然。在这条道路上，我很幸运，遇到了能够指引方向的学长，遇到了真正能帮助同学的老师们… 虽然新的一届大概率会增加新的要求，但希望真正有想法的学弟学妹们，能够攻坚克难，实现自己的内心想法。走过这条路会发现，新的道路已经开始。

2023.7.20记

Veröffentlicht am Bearbeitet am

时间空间复杂度

常对幂指阶
O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(2^n)<O(n!)<O(n^n)$

指针基础概念

&取地址符 *间接运算符

1
2
3
int number = 1;
int *p = &number;//声明一个int类型的指针指向number 存储着number的地址
printf("%d",*p);//输出指针p对应地址的值

malloc函数动态分配的空间需要手动free掉，属于内存中的堆区，系统不会自动回收空间，所以malloc和free的操作是成对出现的。

点操作符.与箭头操作符->的区别

相同点：两个都是二元操作符，其右操作符是成员的名称
不同点：点操作符左边的操作数是一个“结果为结构”的表达式；
箭头操作符左边的操作数是一个指向结构的指针

线性表

线性表的插入删除O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
void ListInsert(SqList *L,int i,int e){
    for(int j=L->length;j>=i;j--){
        L->data[j]=L->data[j-1];
    }
    L->data[i-1]=e;
    L->length++;
}
void ListDelete(SqList *L,int i){
    for(int j=i;j<L->length;j++){
        L->data[j]=L->data[j+1];
    }
    L->length--;
}

单链表

节点的创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct LNode{
    int val;
    struct LNode *next;
};
//typedef <数据类型> <别名>
typedef struct LNode Lnode,*LinkList;
bool InitList(LinkList L){
    L=(LNode*)malloc(sizeof(LNode));
    if(L==NULL)//内存不足
        return false;
    L->val=0;
    L->next=NULL;
    return true;
}
bool empty(LinkList L){
    if(L->next==NULL)
        return true;
    return false;
}

节点的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool ListInsert(LinkList L,int i,int e){//在第i个结点插入值e
    if(i<1)return false;
    //返回第i-1个结点
    LNode *p=GetElem(L,i-1);
    //在结点p后面插入值为e的结点
    InsertNextNode(p,e);
}
bool InsertNextNode(LNode *p,int e){//在节点p后插元素e结点
    if(p==NULL)return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->val=e;
    s->next=p->next;
    p->next=s;
    return true;
}
bool InsertPriorNode(LNode *p,int e){//在p结点前e的结点
    if(p==NULL)return false;
    LNode *s=(LNode *)malloc(sizeof(e));
    if(s==NULL)return false;
    //在p结点之后插入值为e的结点 再交换p的值和e
    s-next=p->next;
    p->next=s;

    s->val=p->val;
    p->val=e;
}

单链表的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LNode *GetElem(LinkList L,int i){//返回第i个结点
    if(i==0)return L;
    int j=0;
    LNode *p=L->next;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    if(p==NULL)return NULL;
    return p;
}
LNode *LocateElem(LinkList L,int e){//返回数据域为e的结点
    int j=0;
    LNode *p=L->next;
    while(p!=NULL&&p->val!=e){
        p=p->next;
    }
    return p;
}

链表的头插法尾插法存储

头插法可以实现链表的逆置:

1
2
3
4
5
6
7
8
9
LinkList List_HeadInsert(LinkList L){
    L=(LNode *)malloc(sizeof(LNode));
    L->next=NULL;
    int t;
    while(scanf("%d")!=EOF){
        InsertNextNode(L,t);
    }
    
}

尾插法:

1
2
3
4
5
6
7
8
9
10
11
12
13
LinkList List_TailInsert(LinkList L){
    int t;
    L=(LNode *)malloc(sizeof(LNode));
    LNode *r=L;//表尾指针
    while(scanf("%d",&t)!=EOF){
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->val=t;
        r->next=s;
        r=s;
    }
    r->next=NULL;
    return L;
}

后缀表达式

将中缀表达式转换为后缀表达式

input:    2+3*(7-4)+8/4
output:   2 3 7 4 - * + 8 4 / +

从左到右遍历表达式中每个数字和符号，遇到数字就输出，若是符号则判断它与栈顶符号的优先级，如果是右括号或者优先级不高于（也就是<=）栈顶符号，则栈顶元素依次出栈，然后将当前符号进栈，一直到结束。

1
2
3
4
5
6
int opaIsBiggerThanopb(char a,char b){//判断符号a的优先级是否比b大
    if((a=='*'||a=='/')&&b!='*'&&b!='/'&&b!='('){
        return 1;
    }
    return 0;
}

双链表

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct DNode{
    int val;
    struct DNode *next,*prior;

}DNode,*DLinkList;
bool InitDLinkList(DLinkList L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)return false;
    L->next=NULL;
    L->prior=NULL;
    return true;

}

双链表后插,前插操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool InsertNextDNode(DNode *p,DNode *s){//在p结点后插s结点
    if(p==NULL||s==NULL)return false;
    s->next=p->next;
    if(p->next!=NULL)
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}
bool InsertPriorDNode(DNode *p,DNode *s){//在p结点前插s结点
    if(p==NULL||s==NULL)return false;
    InsertNextDNode(p->next,s);
    return true;
}

双链表后删操作和链表清空操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool DeleteNextDNode(DNode *p){//删除p的后结点
    if(p==NULL||p->next==NULL)return false;
    DNode *s=p->next;
    if(s->next!=NULL)
        s->next->prior=p;
    p->next=s->next;
    free(s);
    return true;
}
void DestoryList(DlinkList L){//清空链表
    while(L->next!=NULL)
        DeleteNextDNode(L);
    free(L);
    L=NULL;
}

顺序表和链表的优劣

总结

顺序存储：占用空间连续，支持随机存取，查找O(1)改变容量不方便，增删操作O(N)
链式存储：离散小空间分配，增删O(1)不可随机存取，查找O(N)，数据密度低

初始化

顺序存储：预分配大片连续空间
静态分配：容量不可改变。系统自动回收空间
动态分配(malloc free)：容量可改变，但移动数据时间长。需要手动free
链式存储：只需要分配一个头指针