首页 > 代码库 > CSU-ACM暑假集训基础组七夕专场
CSU-ACM暑假集训基础组七夕专场
•Problem A Codeforces 20C 最短路(dij,spfa)
•题意：给出一张n个点m条边的无向图 (2 ≤ n ≤ 105, 0 ≤ m ≤ 105)，输出从1到n的任意一条最短路径。
•解法：dijkstra或者spfa，用pre数组记录到达每个点最短距离的前驱结点。
•注意：路径的长度范围是 1 ≤ wi ≤ 106，从1到n的最短路径长度可能超出int范围。
•没有路径从1到达n时要输出-1
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 typedef pair<LL,int> pii; 8 const int maxn = 100010; 9 const int maxm = 200010;10 int v[maxm],next[maxm],w[maxm];11 int first[maxn],pre[maxn],res[maxn],e;12 LL d[maxn];13 14 void init(){15 e = 0;16 memset(first,-1,sizeof(first));17 }18 19 void add_edge(int a,int b,int c){20 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++;21 }22 23 void dijkstra(int src){24 priority_queue <pii,vector<pii>,greater<pii> > q;25 memset(d,-1,sizeof(d));26 d[src] = 0;27 q.push(make_pair(0,src));28 while(!q.empty()){29 while(!q.empty() && q.top().first > d[q.top().second]) q.pop();30 if(q.empty()) break;31 int u = q.top().second;32 q.pop();33 for(int i = first[u];i != -1;i = next[i]){34 if(d[v[i]] > d[u]+w[i] || d[v[i]] == -1){35 d[v[i]] = d[u]+w[i];36 q.push(make_pair(d[v[i]],v[i]));37 pre[v[i]] = u;38 }39 }40 }41 }42 43 int main(){44 init();45 int n,m,a,b,c;46 scanf("%d%d",&n,&m);47 for(int i = 0;i < m;i++){48 scanf("%d%d%d",&a,&b,&c);49 add_edge(a,b,c);50 add_edge(b,a,c);51 }52 dijkstra(1);53 int now = n,cnt = 0;54 if(d[n] == -1){55 printf("-1");56 return 0;57 }58 while(now != 1){59 res[cnt++] = now;60 now = pre[now];61 }62 res[cnt++] = 1;63 for(int i = cnt-1;i >= 0;i--) printf("%d ",res[i]);64 return 0;65 }
•Problem B Codeforces 295B 最短路(floyd)
•题意：对于一个带权有向图，每次删除一个点，要求计算出删除该点前当前图的所有点间的最短距离之和。
•首先，想知道任意两点间最短距离之和应该使用什么算法？
•毫无疑问 Floyd！
•对于删除顺序，我们可以怎么处理？
•可以反过来做。这样就相当于每次添加一个点到图中，然后询问当前图的所有点间最短距离之和。
•对于每次新增加的点v，我们用v对整张图进行松弛操作：d[s][t] = min(d[s][t],d[s][v]+d[v][t])
•对于统计操作，可以暴力枚举。
•整个复杂度为O(n^3)
•注意：本题数据范围可能超过int
1 #include <cstdio> 2 #include <cstring> 3 #define maxn 510 4 typedef long long LL; 5 LL d[maxn][maxn]; 6 int seq[maxn]; 7 LL ans[maxn]; 8 9 inline LL min(LL a,LL b){10 return a < b ? a : b;11 }12 13 void update(int s,int n){14 for(int i = 1;i <= n;i++)15 for(int j = 1;j <= n;j++)16 d[i][j] = min(d[i][s] + d[s][j],d[i][j]);17 }18 19 LL query(int s,int n){20 LL sum = 0;21 for(int i = n,u = seq[i];i >= s;u = seq[--i])22 for(int j = n,v = seq[j];j >= s;v = seq[--j])23 sum += d[u][v];24 return sum;25 }26 27 int main()28 {29 int n;30 while(scanf("%d",&n) != EOF){31 for(int i = 1;i <= n;i++)32 for(int j = 1;j <= n;j++)33 scanf("%I64d",&d[i][j]);34 for(int i = 1;i <= n;i++)35 scanf("%d",&seq[i]);36 for(int i = n;i >= 1;i--){37 update(seq[i],n);38 ans[i] = query(i,n);39 }40 for(int i = 1;i <= n;i++)41 printf("%I64d ",ans[i]);42 printf("\n");43 }44 return 0;45 }
•Problem C SPOJ MULTQ3 线段树
•题意：有一个长为N(N<=10^5)的数组，初始时数组每个元素的值都为0，接下来有Q(Q<=10^5)次操作，每次操作有2中类型：
•0 A B 将[A,B]区间内的所有数字+1
•1 A B 输出[A,B]区间内所有能够被3整除的数组元素的个数
•考察内容：
•线段树的基本应用
•区间维护
•Lazy标记的使用
•每次修改时，如果某个节点表示的区间[x,y]被加了1，那么我们要对这个区间的3个sum属性进行修改，同时在这个区间打上lazy标记，表示这个区间已经被修改了。
•当需要访问这个节点下面的节点的时候，一定会先经过这个点，这时候下传lazy标记，来保证子节点的信息是正确的。
1 #include <cstdio> 2 const int maxn = 100010; 3 int sum[maxn<<2][3],add[maxn<<2]; 4 5 void pushup(int cur){ 6 int ls = cur<<1,rs = cur<<1|1; 7 sum[cur][0] = sum[ls][0]+sum[rs][0]; 8 sum[cur][1] = sum[ls][1]+sum[rs][1]; 9 sum[cur][2] = sum[ls][2]+sum[rs][2];10 }11 12 void pushdown(int cur){13 int ls = cur<<1,rs = cur<<1|1,tmp;14 if(add[cur] != 0){15 add[ls] = (add[ls]+add[cur])%3;16 add[rs] = (add[rs]+add[cur])%3;17 if(add[cur] == 1){18 tmp = sum[ls][2];19 sum[ls][2] = sum[ls][1];20 sum[ls][1] = sum[ls][0];21 sum[ls][0] = tmp;22 }else if(add[cur] == 2){23 tmp = sum[ls][0];24 sum[ls][0] = sum[ls][1];25 sum[ls][1] = sum[ls][2];26 sum[ls][2] = tmp;27 }28 if(add[cur] == 1){29 tmp = sum[rs][2];30 sum[rs][2] = sum[rs][1];31 sum[rs][1] = sum[rs][0];32 sum[rs][0] = tmp;33 }else if(add[cur] == 2){34 tmp = sum[rs][0];35 sum[rs][0] = sum[rs][1];36 sum[rs][1] = sum[rs][2];37 sum[rs][2] = tmp;38 }39 add[cur] = 0;40 }41 }42 43 void bulid(int cur,int x,int y){44 int mid = (x+y)>>1,ls = cur<<1,rs = cur<<1|1;45 if(x == y){46 sum[cur][0] = 1;47 return;48 }49 bulid(ls,x,mid);50 bulid(rs,mid+1,y);51 pushup(cur);52 }53 54 void update(int cur,int x,int y,int s,int t){55 int mid = (x+y)>>1,ls = cur<<1,rs = cur<<1|1;56 if(x >= s && y <= t){57 int tmp = sum[cur][2];58 sum[cur][2] = sum[cur][1];59 sum[cur][1] = sum[cur][0];60 sum[cur][0] = tmp;61 add[cur] = (add[cur]+1)%3;62 return;63 }64 pushdown(cur);65 if(mid >= s) update(ls,x,mid,s,t);66 if(mid+1 <= t) update(rs,mid+1,y,s,t);67 pushup(cur);68 }69 70 void query(int cur,int x,int y,int s,int t,int &ans){71 int mid = (x+y)>>1,ls = cur<<1,rs = cur<<1|1;72 if(x >= s && y <= t){73 ans += sum[cur][0];74 return;75 }76 pushdown(cur);77 if(mid >= s) query(ls,x,mid,s,t,ans);78 if(mid+1 <= t) query(rs,mid+1,y,s,t,ans);79 }80 81 int main(){82 int n,q,op,a,b;83 scanf("%d%d",&n,&q);84 bulid(1,0,n-1);85 while(q--){86 scanf("%d%d%d",&op,&a,&b);87 if(op == 0) update(1,0,n-1,a,b);88 else{89 int ans = 0;90 query(1,0,n-1,a,b,ans);91 printf("%d\n",ans);92 }93 }94 return 0;95 }
•Problem D Codeforces 4C Map
•题意：输入一个单词，查询字典内是否含有这个单词，如果没有，输出“OK”，将这个新单词插入字典中。如果有，输出做这个单词，后面紧接着输出这个单词出现的次数。
•考察内容：Map的使用
1 #include <iostream> 2 #include <string> 3 #include <map> 4 using namespace std; 5 map<string,int> m; 6 7 int main(){ 8 int n,a; 9 string str;10 cin>>n;11 while(n--){12 cin>>str;13 a = m[str]++;14 if(a) cout<<str<<a<<endl;15 else cout<<"OK"<<endl;16 }17 return 0;18 }
•Problem E SPOJ ROCK DP
•题意：有一块n个单位长的糖，有的地方是甜的(1)，有的地方是酸的(0)。你可以将整块糖任意切成若干段。小盆友们只会买走甜的长度比酸的长度多的那段糖。问经过切割后，最多可以卖掉多少单位长度的糖。
•考察知识：DP
•dp(i)表示将前i段糖进行切割后最多能卖掉的数量
•状态转移方程：
•考虑在第j段之前切一刀
•dp(i)=max{ dp(i) , dp(j-1) +i–j+1}
•( 1 <= j <= i 且在[j,i]区间内甜的比酸的多)
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 205; 6 char str[maxn]; 7 int dp[maxn],sum[maxn][2]; 8 9 int main(){10 int T,len;11 scanf("%d",&T);12 while(T--){13 scanf("%d %s",&len,str+1);14 sum[0][0] = sum[0][1] = 0;15 for(int i = 1;i <= len;i++){16 sum[i][0] = sum[i-1][0];17 sum[i][1] = sum[i-1][1];18 sum[i][str[i]-‘0‘]++;19 }20 dp[0] = 0;21 for(int i = 1;i <= len;i++){22 dp[i] = dp[i-1];23 for(int j = 1;j <= i;j++){24 int sum0 = sum[i][0]-sum[j-1][0];25 int sum1 = sum[i][1]-sum[j-1][1];26 if(sum1 <= sum0) continue;27 dp[i] = max(dp[i],dp[j-1]+i-j+1);28 }29 }30 printf("%d\n",dp[len]);31 }32 return 0;33 }
•Problem F SPOJ NITK06 模拟
•题意：给出一个长为n的数列ai(1<=i<=n)，每个元素都非负。每次你可以选择一个下标x(1<=x<=n-1)，将ax和ax+1同时减1。问经过若干次操作，能否将原数列变成一个元素全部为0的序列。
•模拟即可。
•从数列第一个元素开始，用它剩下的值减去下一个元素的值
•最后如果所有元素都能变为0，则满足条件。
1 #include <cstdio> 2 int a[10010]; 3 4 int main(){ 5 int T,n; 6 scanf("%d",&T); 7 while(T--){ 8 scanf("%d",&n); 9 for(int i = 0;i < n;i++) scanf("%d",&a[i]);10 if(n == 1){11 if(a[0] == 0) printf("YES\n");12 else printf("NO\n");13 continue;14 }15 bool flag = 0;16 for(int i = 0;i < n-1;i++){17 if(a[i] < 0){18 flag = 1;19 break;20 }21 a[i+1] -= a[i];22 }23 if(a[n-1] != 0) flag = 1;24 if(flag) printf("NO\n");25 else printf("YES\n");26 }27 return 0;28 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。