A

愉快的签到题OvO

#include <cstdio>
using namespace std;
int main(){
    int T,n;
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        printf("%d\n",(n+1)/2+1);
    }
}

B

手模一下发现每次最后一步操作都是走最后一行或最后一列

组合数算一下就行了

#include<bits/stdc++.h>
using namespace std;
int f[11][11],i,j,n,m;
int fac[4000010];
const int mod=1000000007;
int mi(int x,int y){
	if (y==0)return 1;
	int t=mi(x,y>>1);
	t=1ll*t*t%mod;
	if (y&1)t=1ll*t*x%mod;
	return t;
}
int C(int x,int y){
	return 1ll*fac[x]*mi(fac[y],mod-2)%mod*mi(fac[x-y],mod-2)%mod;
}
int main()
{
	//srand(time(0));
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	//int T; cin>>T; while(T--) work();
	int T;scanf("%d",&T);
		fac[0]=1;for (i=1;i<=2000000;i++)fac[i]=1ll*fac[i-1]*i%mod;
	while (T--){
	scanf("%d%d",&n,&m);
		if (n<m)swap(n,m);
		if (m==1){printf("2\n");continue;}
		if (m==2){printf("%d\n",4*n);continue;}
		int ans=4ll*C(n+m-2,n-1)%mod;
		printf("%d\n",ans);
	}
	return 0;
}

C

dfs从终点找起点,再减去路径长度不满足条件的

#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int a[1010][1010];
int en[1010][1010],be[1010][1010];
int cnt[1010][1010];
int i,j,k,n,m,x,y,t;
queue<pair<int,int> >q;
bool chk_be(int x,int y){
	if (a[x][y]!=a[x-1][y]+1&&a[x][y]!=a[x+1][y]+1&&a[x][y]!=a[x][y-1]+1&&a[x][y]!=a[x][y+1]+1)return 1;
	return 0;
}
bool chk_en(int x,int y){
	if (a[x][y]!=a[x-1][y]-1&&a[x][y]!=a[x+1][y]-1&&a[x][y]!=a[x][y-1]-1&&a[x][y]!=a[x][y+1]-1)return 1;
	return 0;
}
int dfs(int x,int y){
	if (cnt[x][y])return cnt[x][y];
	if (be[x][y])return cnt[x][y]=1;
	if (a[x-1][y]+1==a[x][y])cnt[x][y]=(cnt[x][y]+dfs(x-1,y))%mod;
	if (a[x+1][y]+1==a[x][y])cnt[x][y]=(cnt[x][y]+dfs(x+1,y))%mod;
	if (a[x][y-1]+1==a[x][y])cnt[x][y]=(cnt[x][y]+dfs(x,y-1))%mod;
	if (a[x][y+1]+1==a[x][y])cnt[x][y]=(cnt[x][y]+dfs(x,y+1))%mod;
	return cnt[x][y];
}
int DFS(int x,int y,int t){
	if (en[x][y])return 1;
	if (t==3)return 0;
	int cnt=0;
	if (a[x-1][y]-1==a[x][y])cnt+=DFS(x-1,y,t+1);
	if (a[x+1][y]-1==a[x][y])cnt+=DFS(x+1,y,t+1);
	if (a[x][y-1]-1==a[x][y])cnt+=DFS(x,y-1,t+1);
	if (a[x][y+1]-1==a[x][y])cnt+=DFS(x,y+1,t+1);
	return cnt;
}
int main(){
	scanf("%d%d",&n,&m);
	for (i=0;i<=n+1;i++)a[i][0]=a[i][m+1]=-100000002;
	for (i=0;i<=m+1;i++)a[0][i]=a[n+1][i]=-100000002;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		}
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++){
			if (chk_be(i,j))be[i][j]=1;
			if (chk_en(i,j))en[i][j]=1;
		}
	int ans=0;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			if (en[i][j]){
				ans=(ans+dfs(i,j))%mod;
			}
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			if (be[i][j])ans=(ans-DFS(i,j,1)+mod)%mod;
	printf("%d\n",ans);
	return 0;
}

H

如果A>B+C,那么只要问问题3就可以知道公主在哪

否则对于问题一二,BC可以回答的跟A一样,这样就没法判断了

#include <cstdio>
using namespace std;
int a,b,c;
int main(){
    scanf("%d%d%d",&a,&b,&c);
    if (a==1&&b==0&&c==0)printf("YES\n0\n");
    else if (a>(b+c))printf("YES\n%d\n",b+c+b+c+1);
    else printf("NO\n");
}

I

考虑50的正整数拆分不是很大。。。就暴力DP

学习了unordered_map,其内部是一个哈希表,所以会快很多

#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;
const int mod=1000000007;
const int seed=131;
int i,j,k,n,m,x,y,t,a[51];
int fac[100010],a0,ans,mx;
unordered_map<ull,int>DP;
int DFS(int sum,int nn){
    if (sum>=mx||nn==n){
        return fac[n-a[0]-nn];
    }
    ull hash=nn;
    for (int i=50;i>=0;i--)hash=hash*seed+a[i];
    if (DP.find(hash)!=DP.end())return DP[hash];
    int ans=0;
    for (int i=1;i<=sum;i++)
        if (a[i]){
            a[i]--;
            ans=(ans+1ll*(a[i]+1)*DFS(sum+i,nn+1)%mod)%mod;
            a[i]++;
        }
    return DP[hash]=ans;
}
int mi(int x,int y){
    if (y==0)return 1;
    int t=mi(x,y>>1);
    t=1ll*t*t%mod;
    if (y&1)t=1ll*t*x%mod;
    return t;
}
int A(int x,int y){
    return 1ll*fac[x]*mi(fac[x-y],mod-2)%mod;
}
int main(){
    scanf("%d",&n);
    fac[0]=1;for (i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    scanf("%d",&a0);
    for (i=1;i<=n;i++){
        scanf("%d",&x);
        a[x]++;mx=max(mx,x);
    }
    if (a0==0&&a[0]==n){
        printf("%d\n",fac[n]);
        return 0;
    }
    ans=1ll*DFS(a0,0)*A(n,a[0])%mod;
    printf("%d\n",ans);
    return 0;
}

J

最大二分图权匹配。。。不大会N^3的KM算法。。直接抄板子了。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=810;
typedef long long ll;
int i,j,k,n,m,x,y,t,p[N],ans,w[N][N];
ll a[N],b[N],c[N];
int ex_a[N],ex_b[N],visa[N],visb[N],mat[N],les[N],fa[N];
int dfs(int x){
    visa[x]=1;
    for (int i=1;i<=n;i++){
        if (visb[i])continue;
        int gap=ex_a[x]+ex_b[i]-w[x][i];
        if (!gap){
            visb[i]=1;fa[i+n]=x;
            if (mat[i]==-1)return i+n;
            fa[mat[i]]=i+n;
            int res=dfs(mat[i]);
			if (res>=0)return res;
        }
        else{
            les[x]=min(les[x],gap);
        }
    }
    return -1;
}
int KM(){
    memset(mat,-1,sizeof mat);
    for (int i=1;i<=n;i++){
        ex_a[i]=0;
        for (int j=1;j<=n;j++)
            ex_a[i]=max(ex_a[i],w[i][j]);
    }
    for (int x=1;x<=n;x++){
        for (int i=1;i<=n;i++)les[i]=INF;
        memset(fa,-1,sizeof fa);
        memset(visa,0,sizeof visa);
        memset(visb,0,sizeof visb);
        bool first=1;int end=-1;
        while (1){
            if(first){first=false;end=dfs(x);}
			else{
				for(int i=1;i<=n;i++)if(les[i]==0){les[i]=INF;end=dfs(i);if(end>=0)break;}
			}
			if(end>=0){
				int p=end;
				while(p!=-1){mat[p-n]=fa[p];p=fa[fa[p]];}
				break;
			}
			else{
				int d=INF;
				for(int i=1;i<=n;i++)d=min(d,les[i]);
				for(int i=1;i<=n;i++){
					if(visa[i]){ex_a[i]-=d;les[i]-=d;}
					if(visb[i])ex_b[i]+=d;
				}
			}
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++)ans+=w[mat[i]][i];
    // for (int i=1;i<=n;i++)printf("%d ",mat[i]);printf("\n");
    return ans;
}
int main(){
    scanf("%d",&n);
    for (i=1;i<=n;i++)scanf("%lld",&a[i]);
    for (i=1;i<=n;i++)scanf("%d",&p[i]);
    for (i=1;i<=n;i++)scanf("%lld",&b[i]);
    for (i=1;i<=n;i++)scanf("%lld",&c[i]);
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            int co=0;
            for (k=1;k<=n;k++){
                if (b[i]+c[j]>a[k])co+=p[k];
            }
            w[i][j]=co;
            // printf("%d %d %d\n",i,j,w[i][j]);
        }
    }
    printf("%d\n",KM());
}

K

利用比例的思想来算。。。

注意精度。。。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const double eps=0;
bool on(int x1,int y1,int x2,int y2,int x3,int y3){
    if (x1==x3&&y1==y3)return 1;
    if (x2==x3&&y2==y3)return 1;
    if (x1==x2){
        if (y1>y2)swap(y1,y2);
        if (x1==x3&&y1<=y3&&y3<=y2)return 1;
        return 0;
    }
    if (x1==x3||x2==x3)return 0;
    double k1=1.0*(y2-y1)/(x2-x1);
    double k2=1.0*(y3-y1)/(x3-x1);
    if (fabs(k2-k1)>eps)return 0;
    if (x2<x1)swap(x1,x2);
    // printf("%d %d %d %d %d %d\n",x1,y1,x2,y2,x3,y3);
    if (x1<=x3&&x2>=x3)return 1;
    return 0;
}
void find(int x1,int y1,int x2,int y2,double k){
    // printf("%d %d %d %d %lf\n",x1,y1,x2,y2,k);
    printf("%lf %lf\n",(x2-x1)*k+x1,(y2-y1)*k+y1);
}
int main(){
    int T,x0,y0,x1,y1,x2,y2,x3,y3;
    scanf("%d",&T);
    while (T--){
        scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x0,&y0);
        if (on(x1,y1,x3,y3,x0,y0)){swap(x2,x3);swap(y2,y3);}
        else if (on(x2,y2,x3,y3,x0,y0)){swap(x1,x3);swap(y1,y3);}
        if (!on(x1,y1,x2,y2,x0,y0)){printf("-1\n");continue;}
        // printf("%d %d %d %d\n",x1,y1,x2,y2);
        if (x1==x2){
            if (y1>y2){swap(y1,y2);}
            if (2*(y2-y0)==y2-y1)printf("%d %d\n",x3,y3);
            else if (2*(y2-y0)>y2-y1){
                find(x2,y2,x3,y3,0.5*(y2-y1)/(y2-y0));
            }
            else find(x1,y1,x3,y3,0.5*(y2-y1)/(y0-y1));
        }
        else{
            if (x1>x2){swap(x1,x2);swap(y1,y2);}
            if (2*(x2-x0)==x2-x1)printf("%d %d\n",x3,y3);
            else if (2*(x2-x0)>x2-x1){
                // printf("!!!\n");
                find(x2,y2,x3,y3,0.5*(x2-x1)/(x2-x0));
            }
            else find(x1,y1,x3,y3,0.5*(x2-x1)/(x0-x1));
        }
    }
}


告别纷扰,去寻找生活的宝藏。