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));
}
}
}
Comments | NOTHING