想了想感觉每次CF都发一篇文章挺浪费的，就把一个月的刷题都总结在这里。想了想，就算不搞ACM，还是尽量把自己cf分保持在1900+能保持算法状态（也有可能是痴心妄想hhhh)
【CF】 Educational Codeforces Round 115 (Rated for Div. 2)
D
如果直接选就是C(n,3)，然后考虑限制条件，可以发现不满足的三元对为(Xa,Ya),(Xa,Yb),(Xb,Yb)然后我们发现三元组中中间那个特别，其余的两个都分别有一个变量与之相同。那么最后找不满足的三元对时，我们枚举中间那个，对于它为中间不满足的就是(cntx[Xa]-1) * (cnty[Yb]-1)，关于cnt预统计一下即可。
点击查看代码
typedef long long ll;
ll n;
int cta[200005],ctb[200005];
int aa[200005],bb[200005];
ll ans;
void sol() {
scanf("%lld",&n);
for(int i=1;i<=n;i++) ctb[i]=cta[i] = 0;
for(int i=1;i<=n;i++) {
int a,b;
scanf("%d%d",&a,&b);
aa[i] = a; bb[i] = b;
cta[a]++; ctb[b]++;
}
ans = 1ll * n * (n-1) * (n-2)/6ll;
for(int i=1;i<=n;i++) {
ans -= 1ll*(cta[aa[i]]-1) * (ctb[bb[i]]-1);
}
printf("%lld\n",ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--) {
sol();
}
}
E
设f[x][y][down/right]表示方案数，最后一个下来是往下转下来还是往右转下来的。有f[x][y][down]=f[x-1][y][right]+1 , f[x][y][right]=f[x][y-1][down]+1,那么可以O(nm)计算出初始的总方案数(注意直接所有方案数加起来把单格子计算了两次)，之后每次修改，因为我们发现对于一个状态转移是唯一的，并且发现每次修改影响的格子并不多，那么我们每次暴力更新一下DP，O(nq)就可以了。
点击查看代码
typedef long long ll;
const int maxn = 1005;
int n,m,q;
ll f[maxn][maxn][2]; //0 down 1 right 是如何到(x,y)
bool blo[maxn][maxn];
ll ANS,freecnt;
void dfs(int x,int y,int did) {
if(blo[x][y]||x>n||y>m) return;
ANS -= f[x][y][did];
if(did==1) {
f[x][y][1] = f[x][y-1][0] + 1;
dfs(x+1,y,0);
}
else {
f[x][y][0] = f[x-1][y][1] + 1;
dfs(x,y+1,1);
}
ANS += f[x][y][did];
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
f[i][j][0] = f[i-1][j][1] + 1;
f[i][j][1] = f[i][j-1][0] + 1;
ANS += f[i][j][0] + f[i][j][1];
}
}
freecnt = 1ll*n*m;
while (q--) {
int x,y;
scanf("%d%d",&x,&y);
if(blo[x][y]){
blo[x][y] ^= 1;
f[x][y][0] = f[x-1][y][1]+1;
f[x][y][1] = f[x][y-1][0]+1;
ANS+=f[x][y][0]+f[x][y][1];
dfs(x+1,y,0);
dfs(x,y+1,1);
freecnt++;
}
else {
blo[x][y] ^= 1;
ANS -= f[x][y][0] + f[x][y][1];
f[x][y][0] = f[x][y][1] = 0;
dfs(x+1,y,0);
dfs(x,y+1,1);
freecnt--;
}
printf("%lld\n",ANS-freecnt);
}
return 0;
}
Codeforces Round #745 (Div. 1)
A
突然发现出题者是我母校的学弟大佬，%%%
没做出来，本题基本参考
仔细分析发现这好像就是求O（N^3)最大二维前缀和？枚举上界，下界，然后枚举r，顺便更新最优前缀和，来避免O(n^4)枚举。。。还是太菜了。
点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
#include<random>
#include<ctime>
#include<complex>
#include<iomanip>
using namespace std;
const int maxn = 405;
int n,m;
char ss[maxn];
int a[maxn][maxn],sm[maxn][maxn];
int gsum(int xa,int ya,int xb,int yb) {
return sm[xb][yb] - sm[xa-1][yb] - sm[xb][ya-1] + sm[xa-1][ya-1];
}
int ANS;
int hanbao(int xa,int ya,int xb,int yb) {
return gsum(xa+1,ya,xb-1,yb) + (yb-ya+1)*2-gsum(xa,ya,xa,yb)-gsum(xb,ya,xb,yb);
}
int clac(int up,int dw,int i) {
return dw-up-1-gsum(up+1,i,dw-1,i);
}
void sol() {
scanf("%d%d",&n,&m);
ANS = n*m;
for(int i=1;i<=n;i++) {
scanf("%s",&ss[1]);
for(int j=1;j<=m;j++) {
a[i][j] = ss[j]-'0';
sm[i][j] = sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+a[i][j];
}
}
for(int up=1;up<=n;up++) {
for(int dw=up+4;dw<=n;dw++) {
int maxpre = -n*m;
for(int i=4;i<=m;i++) {
maxpre = max(maxpre,hanbao(up,1,dw,i-3)-clac(up,dw,i-3));
ANS = min(ANS,hanbao(up,1,dw,i-1)+clac(up,dw,i)-maxpre);
}
}
}
printf("%d\n",ANS);
}
int main(){
int t;
scanf("%d",&t);
while(t--) sol();
return 0;
}
Codeforces Round #748 (Div. 3)
div3都打不明白，大概是真的废了。
D2
做法有两个。。一个是n^5(实际完全打不到)，一个是2e6*n。
第一个做法就是设背包s[i][k]表示从1到i,取了k个数，包含的所有公共gcd,（把它们全部放在set里)，然后每次扩展往后取就可以了。这样我们就可以从s[x][n/2]中找到满足的最大答案
第二个做法。。直接爆枚所有的mod，然后O(n）验证。。。。（考场上真是*没想到cxxx）。
法一
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
#include<random>
#include<ctime>
#include<complex>
#include<iomanip>
using namespace std;
int gcd(int a,int b) {
return (!b)?a:gcd(b,a%b);
}
int n;
int a[45];
set<int>se[45][45];
void sol() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
se[0][0].insert(0);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) se[i][j].clear();
}
for(int i=1;i<=n;i++) {
for(int j=0;j<=i-1;j++) {
for(int k=1;k<=i;k++) {
for(auto it:se[j][k-1]) {
int oo;
if(j==0) oo = 0;
else oo = gcd(a[i]-a[j],it);
if(!se[i][k].count(oo))
se[i][k].insert(oo);
}
}
}
}
int ANS = 1;
for(int i=n/2;i<=n;i++) {
if(!se[i][n/2].empty()) {
if(*se[i][n/2].begin()==0) {
puts("-1"); return;
}
ANS = max(ANS,*se[i][n/2].rbegin());
}
}
printf("%d\n",ANS);
}
int main() {
int t;
scanf("%d",&t);
while(t--) sol();
}
2
法二
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
#include<random>
#include<ctime>
#include<complex>
#include<iomanip>
using namespace std;
const int MM = 2000005;
int n;
int a[45],b[45]; int cnt[MM];
void sol() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int mod = MM;mod>=1;mod--) {
int bst = 0;
for(int i=1;i<=n;i++) {
b[i] = a[i]%mod;
if(b[i]<0) b[i]+=mod;
cnt[b[i]]++;
bst = max(bst,cnt[b[i]]);
}
for(int i=1;i<=n;i++) cnt[b[i]]--;
if(bst>=n/2) {
if(mod==MM) puts("-1");
else printf("%d\n",mod);
return;
}
}
}
int main(){
int t;
scanf("%d",&t);
while (t--) {
sol();
}
return 0;
}