规律总结：联考必爆炸
T1 2A
没$A$掉的大水题，但是是真的不知道$000$前面的$00$也算先导$0$，以后要长记性，这种东西不能再错了
再打三遍：
$000$前面的$00$也算先导$0$
$000$前面的$00$也算先导$0$
$000$前面的$00$也算先导$0$
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int NN=100,inf=0x3fffffff;
5 int n,stk[NN],top,len,tmp[NN][NN],dian;
6 char s[NN];
7 bool check=0;
8
9 namespace WSN{
10 inline short main(){
11 freopen("ip.in","r",stdin);
12 freopen("ip.out","w",stdout);
13 scanf("%s",s+1);n=strlen(s+1);
14
15 for(int i=1;i<=n;i++){
16 int j=i,num=0,pw=1; bool f=0; top=0;
17 while(j<=n&&'0'<=s[j]&&s[j]<='9'){
18 stk[++top]=s[j]-'0';
19 ++j;
20 }
21 for(int k=top;k;k--){
22 num+=pw*stk[k];pw*=10;
23 if(num>255){f=1;break;}//>255
24 if(stk[1]==0&&top>1){f=1;break;}//pre of 0
25 }
26 if(f){check=1;puts("NO");break;}
27 if(j<=n&&s[j]!='.'&&(s[j]>'9'||s[j]<'0')){check=1;puts("NO");break;}//rest of char
28 if(s[j]=='.'){++dian;}
29 if(dian>3){puts("NO");check=1;break;}//'.'>3
30 i=j;
31 }
32 if(!check){puts("YES");return 0;}
33
34 int tim=0;len=0;
35 for(int i=1;i<=n;i++){
36 int j=i,num=0,pw=1; top=0; bool f=0;
37 while('0'<=s[j]&&s[j]<='9'){
38 stk[++top]=s[j]-'0';
39 ++j;
40 }
41 if(top){
42 ++tim;
43 for(int k=top;k;k--){
44 num+=pw*stk[k]; pw*=10;
45 if(num>255){
46 tmp[tim][1]=2; tmp[tim][2]=5; tmp[tim][3]=5; tmp[tim][0]=3;
47 f=1; break;
48 }
49 if(stk[1]==0&&top>1){
50 int u=1;while(stk[u]==0&&u<=top) ++u;
51 if(u==top+1){
52 tmp[tim][1]=0; tmp[tim][0]=1;
53 f=1; break;
54 }
55 for(;u<=top;u++) tmp[tim][++tmp[tim][0]]=stk[u];
56 f=1; break;
57 }
58 }
59 if(!f) for(int k=1;k<=top;k++) tmp[tim][k]=stk[k],tmp[tim][0]++;
60 }
61 i=j;
62 }
63 for(int i=1;i<=tim;i++){
64 for(int j=1;j<=tmp[i][0];j++) printf("%lld",tmp[i][j]);
65 if(i!=tim) printf(".");
66 } puts("");
67 return 0;
68 }
69 }
70 signed main(){return WSN::main();}
View Code
T2 2B
看成了$dp$，去打了$T3$，十分钟冲了一发暴力走人了（貌似这是我考场上第二次把大水题看成$dp$，上次好像还是联考？）
贪心的考虑删$AP$肯定最后剩的少，实在不行的时候再删$PP$
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int NN=1e4+5,inf=0x3fffffff;
5 int n,a1,a2;
6 char s[NN];
7
8 namespace WSN{
9 inline short main(){
10 freopen("apstr.in","r",stdin);
11 freopen("apstr.out","w",stdout);
12 scanf("%s",s+1); n=strlen(s+1);
13 for(int i=1;i<=n;i++){
14 if(s[i]=='A') ++a1;
15 else{
16 if(!a1) a2++;
17 else a1--;
18 }
19 }
20 if(a2&1) cout<<a1+1<<endl;
21 else cout<<a1<<endl;
22 return 0;
23 }
24 }
25 signed main(){return WSN::main();}
View Code
T3 2C
第一，二种情况直接可以用$\textit{unordered_map}$搞过，考虑菱形的时候
使用$bitset$记录一下每个节点的所有的爹，然后枚举当前节点$x$的任意两个直接爹取交集
不为空就证明之前肯定是一个有菱形的形状，但是还要看看两个爹之间是否有连边，如果没有就是真菱形
其实所有的判断条件题目里面都给了，就是看代码实现细节，（比如不合法要清零。。。。）
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 int n,tim,cnt;
5 string s,t[1005];
6 unordered_map<string,int> mp;
7 bitset<1005> vis[1005];
8 namespace WSN{
9 inline short main(){
10 freopen("class.in","r",stdin);
11 freopen("class.out","w",stdout);
12 cin>>n;
13 for(int w=1;w<=n;w++){
14 cin>>s; char c; cin>>c; bool f=0;
15 tim=0; if(mp[s]!=0) f=1;
16 while(1){
17 cin>>t[++tim];if(t[tim][0]==';') break;
18 if(f==0&&mp[t[tim]]==0) f=1;
19 } --tim;
20 if(f){puts("greska");continue;}
21 mp[s]=++cnt; int x=mp[s]; f=0;
22 for(int i=1;i<tim;i++){
23 for(int j=i+1;j<=tim;j++){
24 int y=mp[t[i]],z=mp[t[j]];
25 bitset<1005> t=vis[y]&vis[z];
26 if(!t.none()&&!vis[y][z]&&!vis[z][y]){f=1;break;}
27 } if(f) break;
28 }
29 if(f){puts("greska");mp[s]=0;--cnt;continue;}
30 for(int i=1;i<=tim;i++)
31 vis[x]|=vis[mp[t[i]]],vis[x][mp[t[i]]]=1;
32 puts("ok");
33 }
34 return 0;
35 }
36 }
37 signed main(){return WSN::main();}
View Code
T4 2D
按照题解上的做，然后就是处理$vis$数组的时候有细节
要记录一个$part$数组表示值域开始不同的分界，然后处理$vis$的时候维护$part$数组即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(LL x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14
15 const int NN=1e6+5;
16 int n,m,M,N,B,deg[NN],fa[NN];
17 vector<int> e[NN];
18 struct SNOW{int id,d;}p[NN],a[NN];
19 int rk[NN],bin[NN],part[NN],vis[NN];
20 LL ansk,ans=-1e18;
21 inline int getfa(int x){return fa[x]=((fa[x]==x)?x:getfa(fa[x]));}
22 inline void pre(){
23 for(int i=1;i<=n;i++) p[i].id=i,p[i].d=deg[i];
24 for(int i=1;i<=n;i++) ++bin[p[i].d];
25 for(int i=1;i<=n;i++) bin[i]+=bin[i-1];
26 for(int i=n;i;i--) rk[i]=bin[p[i].d]--;
27 for(int i=1;i<=n;i++) a[rk[i]]=p[i];
28 for(int i=1;i<=n-1;i++) if(a[i].d!=a[i+1].d) part[a[i].d]=i;
29 for(int i=1;i<=n;i++) for(auto y:e[a[i].id]) if(a[rk[y]].d>a[i].d){
30 --a[rk[y]].d; int pos=part[a[rk[y]].d]+1;
31 part[a[rk[y]].d]++;int id=a[pos].id;
32 swap(a[rk[id]],a[rk[y]]); swap(rk[id],rk[y]);
33 }
34 for(int i=1;i<=n;i++) vis[a[i].id]=a[i].d;
35 // for(int i=1;i<=n;i++) cout<<vis[i]<<endl;
36 }
37 int ns[NN],ds[NN],ms[NN];
38 inline void get(){
39 for(int i=1;i<=n;i++) bin[i]=0,rk[i]=0;
40 for(int i=1;i<=n;i++) ++bin[vis[i]];
41 for(int i=1;i<=n;i++) bin[i]+=bin[i-1];
42 for(int i=n;i;i--) rk[i]=bin[vis[i]]--;
43 for(int i=1;i<=n;i++) bin[rk[i]]=i;
44 for(int i=1;i<=n;i++) ns[i]=1,ds[i]=deg[i];
45 // for(int i=1;i<=n;i++) cout<<ns[i]<<" "<<ds[i]<<endl;
46 for(int i=1;i<=n;i++) fa[i]=i;
47 }
48
49 namespace WSN{
50 inline short main(){
51 freopen("kdgraph.in","r",stdin);
52 freopen("kdgraph.out","w",stdout);
53 n=read(); m=read(); M=read(); N=read(); B=read();
54 for(int i=1;i<=m;i++){
55 int u=read(),v=read(); ++deg[u]; ++deg[v];
56 e[u].push_back(v); e[v].push_back(u);
57 }
58 pre(); get();
59 for(int i=n;i;i--){
60 int x=bin[i],X=getfa(x);
61 for(auto y:e[x]) if(rk[y]>=rk[x]){
62 int Y=getfa(y);
63 if(X!=Y){
64 if(ns[X]<=ns[Y]) swap(X,Y);
65 ns[X]+=ns[Y]; ds[X]+=ds[Y]; ms[X]+=ms[Y]; fa[Y]=X;
66 } ms[X]++;
67 }
68 if(vis[x]!=vis[bin[i-1]]){
69 for(int j=i;j<=n&&vis[x]==vis[bin[j]];j++){
70 int FA=getfa(bin[j]);
71 LL val=1ll*M*ms[FA]-1ll*N*ns[FA]+1ll*B*(ds[FA]-(ms[FA]<<1));
72 if(val>ans){ ans=val; ansk=1ll*vis[x]; }
73 }
74 }
75 }
76 write(ansk,' ');write(ans);
77 return 0;
78 }
79 }
80 signed main(){return WSN::main();}
View Code