先猜后证|只猜不证

路径长度和最大值有关问题往往猜测与直径有关。

http://codeforces.com/contest/911/submission/34173244

化不合法为不优

O(time)->O(ans)

http://www.lydsy.com/JudgeOnline/problem.php?id=4716

正解是用个堆,然而有个非常高明的”暴力“。

#pragma GCC optimize("O2")
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for (register int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
typedef long long ll;
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> vec;
inline void read(int &x) {
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
const int N = 1050;
int n,m,xmn,ymn,k;
int a[N][N];
ll s[N][N];
inline ll getsum(int x0, int y0, int x1, int y1) {
    x0--; y0--;
    return s[x1][y1]-s[x0][y1]-s[x1][y0]+s[x0][y0];
}
inline int getans(int val) { //"<=val"
    int res=0; //if (res>=k) return res;
    rep(i,1,n-xmn+1) rep(j,1,m-ymn+1) {
        register int x=i+xmn-1,y=j+ymn-1;
        for (;x<=n;x++) {
            if (getsum(i,j,x,y)>val) break;
            rep(Y,y,m) {
                if (getsum(i,j,x,Y)>val) break;
                res++; if (res>=k) return res;
            }
        }
    }
    return res;
}
int main() {
    read(n); read(m); read(xmn); read(ymn); read(k);
    rep(i,1,n) rep(j,1,m) read(a[i][j]);
    rep(i,1,n) rep(j,1,m) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    int l=0,r=n*m*2000;
    while (l<r) {
        register int mid=(1LL*l+r)>>1;
        if (getans(mid)<k) l=mid+1; else r=mid;
    }
    printf("%d",l+1);
    return 0;
}

可以证明,每次getans函数,里面有用的解只有O(k)个,没用的解(多余的复杂度)也只有O(k+nm)个,所以复杂度是O(nm+k)。

找规律

BZOJ1228

这个SG规律真难找,找了半天也找不出最后看了题解。

这个规律不是O(1)的,是O(log)的。

SG[i/2][j/2]->SG[i][j]

int GetSG(int n,int m){
    if((n&1)&&(m&1)) return 0;
    if(!(n&1)&&!(m&1)) return GetSG(n/2,m/2)+1;
    return (n&1)?GetSG((n+1)/2,m/2)+1:GetSG(n/2,(m+1)/2)+1;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int tmp[500010],ts,mex,sg[555][555];
int main(){
	FOR(t,2,60)
		FOR(j,1,t-1){
			int i=t-j;
			ts=0;
			FOR(k,1,i-1) tmp[++ts]=sg[k][i-k];
			FOR(k,1,j-1) tmp[++ts]=sg[k][j-k];
			sort(tmp+1,tmp+ts+1);
			ts=unique(tmp+1,tmp+ts+1)-tmp-1;
			mex=-1;
			FOR(k,1,ts)
				if (tmp[k]==mex+1) ++mex;
			sg[i][j]=mex+1;
		}
	FOR(i,1,30){
		FOR(j,1,30) printf("%d ",sg[i][j]);
		puts("");
	}
	return 0;
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3288

欧拉函数前缀积。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
int n,phi[1000010],p[1000010],pr;
LL ans;
bool u[1000010];
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
void getp(){
	phi[1]=1;
	FOR(i,2,n){
		if (!u[i]){p[++pr]=i;phi[i]=i-1;}
		FOR(j,1,pr){
			if (i*p[j]>n) break;
			u[i*p[j]]=1;
			if (i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
			else phi[i*p[j]]=phi[i]*phi[p[j]];
		}
	}
}
int main(){
	cin>>n;
	getp();
	ans=1;
	FOR(i,1,n) ans=ans*phi[i]%MO;
	cout<<ans<<endl;
	return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
int a[1010][1010],n,k;
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
LL det(){
	LL ans=1;
	FOR(i,1,n){
		k=0;
		FOR(j,i,n)
			if (a[j][i]!=0){k=j;break;}
		if (!k) return 0ll;
		if (i!=k){
			FOR(j,1,n) swap(a[i][j],a[k][j]);
			ans=-ans;
		}
		LL t=pw(a[i][i],MO-2);
		FOR(j,i+1,n)
			if (a[j][i]!=0){
				LL w=-t*a[k][i]%MO;
				FOR(k,i,n) (a[j][k]+=a[i][k]*w)%=MO;
			}
	}
	FOR(i,1,n) ans=ans*a[i][i]%MO;
	return ans;
}
int main(){
	cin>>n;
	FOR(i,1,n)
		FOR(j,1,n)
			a[i][j]=__gcd(i,j);
	cout<<det()<<endl;
	return 0;
}

从数据范围推测算法

以下仅对非TC题适用

 

n<=13

3^n*n^2 http://cwystc.is-programmer.com/posts/211162.html

 

n<=100

随机最大团

 

n<=400

最大流 http://cwystc.is-programmer.com/posts/211145.html

 

k<=n<=50

2^(n/2) 暴力 http://cwystc.is-programmer.com/posts/211416.html

根据k的大小写2种不同复杂度的指数级暴力拼起来 http://cwystc.is-programmer.com/posts/211416.html


n<=1e9,k<=100

矩阵乘法 O(logn*k^3) http://cwystc.is-programmer.com/posts/210962.html

 

n<=1e5,k<=12

bitset O(n*2^k/32) http://cwystc.is-programmer.com/posts/211116.html

 

MO=998244353

NTT

 

n=1e10

杜教筛