整天自闭。
A：有各种讨论方式。我按横坐标排了下然后讨论了下纵坐标单调和不单调两种情况。写了15min也就算了，谁能告诉我printf和cout输出不一样是咋回事啊？又调了10min啊？upd：突然想起来我好像define int long long了
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define int long long char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n; struct data { int x,y; bool operator <(const data&a) const { return x<a.x||x==a.x&&y<a.y; } bool operator ==(const data&a) const { return x==a.x&&y==a.y; } }a[3],ans[1000000]; signed main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d "; #endif for (int i=0;i<3;i++) a[i].x=read(),a[i].y=read(); sort(a,a+3); if (a[0].y<=a[1].y==a[1].y<=a[2].y) { for (int i=min(a[0].y,a[1].y);i<=max(a[0].y,a[1].y);i++) ans[++n].x=a[0].x,ans[n].y=i; for (int i=a[0].x;i<=a[1].x;i++) ans[++n].x=i,ans[n].y=a[1].y; for (int i=min(a[1].y,a[2].y);i<=max(a[1].y,a[2].y);i++) ans[++n].x=a[1].x,ans[n].y=i; for (int i=a[1].x;i<=a[2].x;i++) ans[++n].x=i,ans[n].y=a[2].y; } else { for (int i=a[0].x;i<=a[1].x;i++) ans[++n].x=i,ans[n].y=a[0].y; for (int i=min(a[1].y,a[0].y);i<=max(a[1].y,a[0].y);i++) ans[++n].x=a[1].x,ans[n].y=i; for (int i=min(a[0].y,a[2].y);i<=max(a[0].y,a[2].y);i++) ans[++n].x=a[1].x,ans[n].y=i; for (int i=a[1].x;i<=a[2].x;i++) ans[++n].x=i,ans[n].y=a[2].y; } sort(ans+1,ans+n+1); n=unique(ans+1,ans+n+1)-ans-1; cout<<n<<endl; for (int i=1;i<=n;i++) cout<<ans[i].x<<' '<<ans[i].y<<endl; return 0; }
B：将权值平均分在叶节点的边上即可。感性证明。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define int long long #define N 100010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,p[N],t,degree[N]; struct data{int to,nxt; }edge[N<<1]; void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} signed main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d "; #endif n=read(),m=read(); for (int i=1;i<n;i++) { int x=read(),y=read(); degree[x]++,degree[y]++; } if (n==2) {cout<<m;return 0;} int cnt=0; for (int i=1;i<=n;i++) if (degree[i]==1) cnt++; printf("%.8f",m*2.0/cnt); return 0; }
这个时候就40min了，简直垫底。
C：考虑让置换后的串在不超过上界的前提下尽量大。一旦某一位不卡上界了，后面就只需要贪心地尽量满足下界。于是在每种字符第一次出现的位置考虑卡与不卡两种情况即可。简直是个思博题。但它是个码农题。不明白意义何在。写的丑的没边了。调了30min，最后3min过非常刺激。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define int long long #define N 1000010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int T,n,k,a[N],b[N],c[N],match[27],tmp[27]; char s[N]; bool used[27]; signed main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d "; #endif T=read(); while (T--) { k=read(); scanf("%s",s+1);n=strlen(s+1); for (int i=1;i<=n;i++) a[i]=s[i]-'a'+1; scanf("%s",s+1); for (int i=1;i<=n;i++) b[i]=s[i]-'a'+1; scanf("%s",s+1); for (int i=1;i<=n;i++) c[i]=s[i]-'a'+1; memset(match,0,sizeof(match));memset(used,0,sizeof(used)); bool flag=0; for (int i=1;i<=n;i++) { if (!match[a[i]]) { for (int x=c[i]-1;x>=1;x--) if (!used[x]) { for (int j=1;j<=k;j++) tmp[j]=match[j]; match[a[i]]=x;used[x]=1; bool islim=1;flag=1; for (int j=1;j<=n;j++) { if (match[a[j]]&&match[a[j]]>b[j]) islim=0; if (islim&&match[a[j]]&&match[a[j]]<b[j]) {flag=0;break;} if (!match[a[j]]) { if (!islim) { for (int x=k;x>=1;x--) if (!used[x]) {match[a[j]]=x,used[x]=1;break;} } else { bool f=1; for (int x=k;x>=1;x--) if (!used[x]) { if (x<b[j]) f=0; else match[a[j]]=x,used[x]=1,islim=x==b[j]; break; } if (!f) {flag=0;break;} } } } if (flag) break; memset(used,0,sizeof(used)); for (int j=1;j<=k;j++) { match[j]=tmp[j]; if (match[j]) used[match[j]]=1; } break; } if (flag) break; if (!used[c[i]]) match[a[i]]=c[i],used[c[i]]=1; else break; } if (match[a[i]]&&(match[a[i]]<c[i]||match[a[i]]==c[i]&&i==n)) { //for (int j=1;j<=k;j++) tmp[j]=match[j]; bool islim=1;flag=1; for (int j=1;j<=n;j++) { if (match[a[j]]&&match[a[j]]>b[j]) islim=0; if (islim&&match[a[j]]&&match[a[j]]<b[j]) {flag=0;break;} if (!match[a[j]]) { if (!islim) { for (int x=k;x>=1;x--) if (!used[x]) {match[a[j]]=x,used[x]=1;break;} } else { bool f=1; for (int x=k;x>=1;x--) if (!used[x]) { if (x<b[j]) f=0; else match[a[j]]=x,used[x]=1,islim=x==b[j]; break; } if (!f) {flag=0;break;} } } } break; /*if (!flag) { memset(used,0,sizeof(used)); for (int j=1;j<=k;j++) { match[j]=tmp[j]; if (match[j]) used[match[j]]=1; } }*/ }//��ȷ����ijλ������С�ڴ�ĵ����� if (match[a[i]]&&match[a[i]]>c[i]) break; if (flag) break; } if (flag) { printf("YES "); for (int i=1;i<=k;i++) if (!match[i]) { for (int x=1;x<=k;x++) if (!used[x]) {match[i]=x,used[x]=1;break;} } for (int i=1;i<=k;i++) putchar(match[i]+'a'-1);printf(" "); } else printf("NO "); } return 0; }
D：考虑什么样的人可能成为冠军。比如这个人出的是石头，那么显然要让出剪刀的尽量去消灭出布的，为了防止剪刀遇上石头又要尽量先让布去消灭其他出石头的。可以发现事实上不用管其他出石头的了，考虑一段石头区间，如果两端有出布的让出布的消灭掉即可，否则其两端都有剪刀，那么这段石头对剪刀没有任何影响。那么只要当前考虑的石头其左右都不是“有出布的但没有出剪刀的”，其就能获得冠军。现在要统计总共有多少人，对石头剪刀布各自算一遍，还是考虑石头，把不合法的石头去掉，显然就是第一个布到第一个剪刀之间和最后一个剪刀到最后一个布之间的（有序）。这玩意好像也不难想而且怎么着也比C好写几倍吧？我能不能向天借个30min啊？
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<set> using namespace std; #define ll long long #define int long long #define N 200010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,tree[3][N],a[N]; char s[N]; int val(char c){if (c=='R') return 0;if (c=='P') return 1;if (c=='S') return 2;} void add(int p,int k,int x){while (k<=n) tree[p][k]+=x,k+=k&-k;} int query(int p,int k){int s=0;while (k) s+=tree[p][k],k-=k&-k;return s;} set<int> q[3]; signed main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d "; #endif n=read(),m=read(); scanf("%s",s+1); for (int i=1;i<=n;i++) add(a[i]=val(s[i]),i,1),q[val(s[i])].insert(i); for (int j=0;j<=m;j++) { if (j){int x=read(),y=val(getc());add(a[x],x,-1),add(y,x,1);q[a[x]].erase(x),a[x]=y,q[a[x]].insert(x);} int ans=0; for (int i=0;i<3;i++) { int sc=(i+2)%3,pp=(i+1)%3; if (q[pp].empty()) ans+=query(i,n); else if (q[sc].empty()) ; else { ans+=query(i,n); set<int>::iterator it=q[sc].begin();int x=*it; it=q[sc].end();it--;int y=*it; it=q[pp].begin();if ((*it)<x) ans-=query(i,x)-query(i,(*it)); it=q[pp].end();it--;if ((*it)>y) ans-=query(i,(*it))-query(i,y); } } printf("%d ",ans); } return 0; }
E：考虑类似数位dp的做法，枚举在哪一行第一次不卡限制，之后的每一行的方案数显然都是错排数量，那么只要求出该行填法数量就可以了，比较麻烦的是该行同时受到上一行限制。这个东西同样考虑枚举在哪个位置第一次不卡限制，剩下位置的方案数可以表示为f[i][j]，即长度为i的排列有j位要求错排（j即两排列的后缀重复元素个数）。当然我们不能枚举第一个不卡限制的位置填什么，而是求一下有多少种填法会使后面的限制（重复元素）减少，树状数组乱搞，这里可能有一些细节问题。最后的问题是如何求f[i][j]，直接dp的话可能不太显然，不过有一种无脑的方法，即写出套路的容斥式子，稍加观察就可以发现可以NTT优化一发，CF机子还开了4s当然不虚。注意第一行特殊讨论一下，求出字典序即可。这个题……算了还是比C难（以及难写？）不少。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 2050 #define P 998244353 #define inv3 332748118 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,a[N][N],wrong[N],fac[N],inv[N],tree[N],f[N][N<<1],u[N<<1],lim[N],id[N],r[N<<1],ans; bool flag1[N],flag2[N]; void ins(int k){while (k<=n) tree[k]++,k+=k&-k;} int query(int k){int s=0;while (k) s+=tree[k],k^=k&-k;return s;} int ksm(int a,int k) { int s=1; for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P; return s; } int C(int n,int m){return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;} void DFT(int *a,int n,int g) { for (int i=0;i<n;i++) if (i<r[i]) swap(a[i],a[r[i]]); for (int i=2;i<=n;i<<=1) { int wn=ksm(g,(P-1)/i); for (int j=0;j<n;j+=i) { int w=1; for (int k=j;k<j+(i>>1);k++,w=1ll*w*wn%P) { int x=a[k],y=1ll*w*a[k+(i>>1)]%P; a[k]=(x+y)%P,a[k+(i>>1)]=(x-y+P)%P; } } } } void mul(int *a,int *b,int n) { for (int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|(i&1)*(n>>1); DFT(a,n,3),DFT(b,n,3); for (int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%P; DFT(a,n,inv3);int t=ksm(n,P-2); for (int i=0;i<n;i++) a[i]=1ll*a[i]*t%P; } void pre() { wrong[0]=1;wrong[1]=0;for (int i=2;i<=n;i++) wrong[i]=1ll*(i-1)*(wrong[i-1]+wrong[i-2])%P; wrong[0]=1;for (int i=1;i<=n;i++) wrong[i]=1ll*wrong[i-1]*wrong[n]%P; fac[0]=1;for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%P; inv[0]=inv[1]=1;for (int i=2;i<=n;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P; for (int i=2;i<=n;i++) inv[i]=1ll*inv[i-1]*inv[i]%P; for (int i=0;i<=n;i++) { int t=1;while (t<=(i<<1)) t<<=1; for (int j=i+1;j<t;j++) u[j]=0; for (int j=0;j<=i;j++) u[j]=j&1?P-inv[j]:inv[j],u[j]=1ll*u[j]*fac[i-j]%P,f[i][j]=inv[j]; mul(f[i],u,t); for (int j=0;j<=i;j++) f[i][j]=1ll*f[i][j]*fac[j]%P; } } int calc(int *a) { memset(tree,0,sizeof(tree));int s=0; for (int i=1;i<=n;i++) s=(s+1ll*fac[n-i]*(a[i]-1-query(a[i])))%P,ins(a[i]); return s; } int calc(int *a,int *b) { memset(tree,0,sizeof(tree));int s=0; memset(flag1,0,sizeof(flag1));memset(flag2,0,sizeof(flag2));lim[n+1]=0; flag2[b[n]]=1; for (int i=n;i>=1;i--) { lim[i]=lim[i+1]; flag1[a[i]]=1;if (flag2[a[i]]) lim[i]++; id[i]=query(b[i]),ins(b[i]); if (a[i]<b[i]&&flag2[a[i]]) id[i]--; flag2[b[i-1]]=1;if (flag1[b[i-1]]) lim[i]++; } memset(flag1,0,sizeof(flag1));memset(flag2,0,sizeof(flag2)); memset(tree,0,sizeof(tree)); for (int i=n;i>=1;i--) { int x=query(b[i]-1); s=(s+1ll*x*f[n-i][lim[i+1]-1])%P; s=(s+1ll*(id[i]-x)*f[n-i][lim[i+1]])%P; flag1[a[i]]=1;if (flag2[a[i]]) ins(a[i]); flag2[b[i]]=1;if (flag1[b[i]]) ins(b[i]); } return s; } int main() { #ifndef ONLINE_JUDGE freopen("e.in","r",stdin); freopen("e.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=read(); pre(); ans=1ll*calc(a[1])*wrong[n-1]%P; for (int i=1;i<n;i++) { int x=calc(a[i],a[i+1]); ans=(ans+1ll*x*wrong[n-i-1])%P; } cout<<ans; return 0; }
我也不知道为什么还能涨分。result：rank 208 rating +7