https://codeforces.com/contest/1581/problem/A
就是 3*3*4*...*(2n)
#include <bits/stdc++.h> using namespace std; #define Ha 1000000007 long long n; void solve() { scanf("%lld",&n); long long ret=1; for (int i=3; i<=n*2; i++) ret=ret*i%Ha; printf("%lld\n",ret); } int main() { int ttt; scanf("%d",&ttt); while (ttt--) { solve(); } return 0; }
https://codeforces.com/contest/1581/problem/B
除了不能成连通图,其它大部分情况都可以(往菊花图那弄就行了),就各种特判咯。
#include <bits/stdc++.h> using namespace std; void solve() { long long n,m,k; scanf("%lld%lld%lld",&n,&m,&k); if (n==1) { if (m==0 && k>=2) puts("YES"); else puts("NO"); return; } if (n==2) { if (m==0) puts("NO"); else if (m==1 && k>=3) puts("YES"); else puts("NO"); return; } if (m<n-1) { puts("NO"); return; } if (m>n*(n-1)/2) { puts("NO"); return; } if (k>=4) { puts("YES"); return; } if (k==3 && m==n*(n-1)/2) { puts("YES"); return; } puts("NO"); return; } int main() { int ttt; scanf("%d",&ttt); while (ttt--) { solve(); } return 0; }
https://codeforces.com/contest/1581/problem/C
用的是三次方的算法。先枚举矩形上下边,然后右边往右扫,随着右边往右,左边也是往右的(即最优的左边不会在之前的左边)。
#include <bits/stdc++.h> using namespace std; #define MAXN 500 int n,m; char a[MAXN][MAXN]; int g[MAXN][MAXN], sg[MAXN][MAXN]; //g: cnt('1') int G(int x1, int y1, int x2, int y2) { return sg[x2][y2]-sg[x1-1][y2]-sg[x2][y1-1]+sg[x1-1][y1-1]; } int fun(int x1, int y1, int x2, int y2) { int ret=0; ret+=2*G(x1+1, y1+1, x2-1, y2-1); ret-=G(x1, y1, x2, y2); ret+=2*(x2-x1+y2-y1); ret-=(a[x1][y1]=='0'); ret-=(a[x1][y2]=='0'); ret-=(a[x2][y1]=='0'); ret-=(a[x2][y2]=='0'); return ret; } void solve() { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) scanf("%s",a[i]+1); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { g[i][j]=sg[i][j]=0; } for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) g[i][j]=g[i][j-1]+(a[i][j]=='1'); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) sg[i][j]= sg[i-1][j]+g[i][j]; int ans=fun(1,1,5,4), tmp; for (int i1=1; i1+4<=n; i1++) { for (int i2=i1+4; i2<=n; i2++) { int cur=ans; int j1=1, j2; for (j2=4; j2<=m; j2++) { if ((tmp = fun(i1, j1, i2, j2)) < cur) { cur=tmp; } while (j2-j1>3 && (tmp = fun(i1,j1+1,i2,j2))<cur) { j1++; cur=tmp; } if ((tmp = fun(i1, j2-3, i2, j2)) < cur) { j1=j2-3; cur=tmp; } ans=min(ans, cur); } } } printf("%d\n",ans); } int main() { int ttt; scanf("%d",&ttt); while (ttt--) { solve(); } return 0; }