[考试反思]1112csp-s模拟测试112：二返
分类:
IT文章
•
2022-08-26 12:43:31
连着两场。。。
![[考试反思]1112csp-s模拟测试112：二返](/default/index/img?u=aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2NvbW1vbi8xNzA4MDA0LzIwMTkxMS8xNzA4MDA0LTIwMTkxMTEyMTkzODI2OTkwLTcwNjA4MzQyOS5wbmc= "[考试反思]1112csp-s模拟测试112：二返")
信心赛。但是题锅了，我也锅了。
然后Day2就不用考了。
T1没开够long long。(a+b+c+0ll)与(0ll+a+b+c)还是有一点区别的。
T2出题人用Windows出数据锅了一片（换行符是
）
T3少写了一个等号-5pts问题不大
然后居然WAK了。其实并不是，还是A了一个的。。。
我把普通平衡树A了
T1：装饰
尽量少浪费。
![]()
1 #include<cstdio>
2 int main(){
3 freopen("decorate.in","r",stdin);freopen("decorate.out","w",stdout);
4 int t;scanf("%d",&t);
5 while(t--){
6 int a,b,c;scanf("%d%d%d",&a,&b,&c);
7 if(b>a)a^=b^=a^=b;
8 if(c>a)c^=a^=c^=a;
9 if(a>b+c+0ll<<1)a=b+c<<1;
10 printf("%lld
",(0ll+a+b+c)/3);
11 }
12 }
View Code
T2：循环依赖
考察读入。注意判出题人是否是Windows系统。
![]()
1 #include<cstdio>
2 #include<map>
3 #include<string>
4 #include<iostream>
5 using namespace std;
6 map<string,int>M;
7 int cnt,fir[3000005],l[3000004],to[3000003],deg[3000003],ec,q[3000003],t,EOL;
8 string read(){
9 string S;cin>>S;
10 char ch=getchar();
11 if(ch=='
'||ch==EOF||ch=='
')EOL=1;
12 return S;
13 }
14 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;deg[b]++;}
15 int main(){
16 freopen("dependency.in","r",stdin);freopen("dependency.out","w",stdout);
17 int T;scanf("%d",&T);
18 while(T--){
19 int n;scanf("%d",&n);getchar();
20 for(int i=1;i<=n;++i){
21 EOL=0;string S=read();
22 if(M.find(S)==M.end())M[S]=++cnt;
23 int ths=M[S];
24 while(!EOL){
25 S=read();
26 if(M.find(S)==M.end())M[S]=++cnt;
27 link(ths,M[S]);
28 }
29 }
30 for(int i=1;i<=cnt;++i)if(!deg[i])q[++t]=i;
31 for(int h=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i]){
32 deg[to[i]]--;if(!deg[to[i]])q[++t]=to[i];
33 }
34 puts(t==cnt?"No":"Yes");
35 for(int i=1;i<=cnt;++i)fir[i]=deg[i]=0;
36 t=cnt=ec=0;M.clear();
37 }
38 }
View Code
![]()
1 #include<cstdio>
2 #include<queue>
3 #include<algorithm>
4 using namespace std;
5 #define inf 0x3fffffffffffffff
6 #define int long long
7 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
8 int n,m,b,s,fir[5005],l[50005],to[50005],w[50005],ec;
9 int dt[5005],Fir[5005],L[50005],To[50005];long long dp[5005][5005],c[5005];
10 void link(int a,int b,int v){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;w[ec]=v;}
11 void Link(int a,int b){L[ec]=Fir[a];Fir[a]=ec;To[ec]=b;}
12 long long cal(int fl,int l,int r){return dp[fl-1][l]+(c[r]-c[l])*(r-l-1);}
13 main(){
14 freopen("assignment.in","r",stdin);freopen("assignment.out","w",stdout);
15 scanf("%lld%lld%lld%lld",&n,&b,&s,&m);
16 for(int i=1,A,B,v;i<=m;++i)scanf("%lld%lld%lld",&A,&B,&v),link(A,B,v),Link(B,A);
17 for(int i=1;i<=n;++i)dt[i]=inf;
18 q.push(make_pair(dt[b+1]=0,b+1));
19 while(!q.empty()){
20 int p=q.top().second,d=q.top().first;q.pop();
21 if(d!=dt[p])continue;
22 for(int i=fir[p];i;i=l[i])if(dt[to[i]]>dt[p]+w[i])
23 q.push(make_pair(dt[to[i]]=dt[p]+w[i],to[i]));
24 }
25 for(int i=1;i<=b;++i)c[i]=dt[i];
26 for(int i=1;i<=n;++i)dt[i]=inf;
27 q.push(make_pair(dt[b+1]=0,b+1));
28 while(!q.empty()){
29 int p=q.top().second,d=q.top().first;q.pop();
30 if(d!=dt[p])continue;
31 for(int i=Fir[p];i;i=L[i])if(dt[To[i]]>dt[p]+w[i])
32 q.push(make_pair(dt[To[i]]=dt[p]+w[i],To[i]));
33 }
34 for(int i=1;i<=b;++i)c[i]+=dt[i];
35 sort(c+1,c+1+b);
36 for(int i=1;i<=b;++i)c[i]+=c[i-1];
37 for(int i=1;i<=b;++i)dp[1][i]=(i-1)*c[i];
38 for(int i=2;i<=s;++i){
39 int ptr=i-1;
40 for(int j=i;j<=b;++j){
41 while(ptr+1<j&&cal(i,ptr,j)>=cal(i,ptr+1,j))ptr++;
42 dp[i][j]=cal(i,ptr,j);
43 }
44 }printf("%lld
",dp[s][b]);
45 }
