A：直接枚举就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1000100; const int INF=1e9+10; ll a,b,c; ll p,q,k,m; int main() { //freopen("in.txt","r",stdin); int T;cin>>T; while(T--){ scanf("%I64d%I64d%I64d",&a,&b,&c); bool flag=0; for(p=1;p*p<=a;p++){ if(a%p) continue; q=a/p; for(k=1;k*k<=c;k++){ if(c%k) continue; m=c/k; if(q*k+m*p==b) flag=1; if(q*m+p*k==b) flag=1; if(flag) break; } if(flag) break; } puts(flag?"YES":"NO"); } return 0; }
B：直接dp差值，比赛的时候复杂度估计错，直接写了3^20...
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=2010; const int INF=1e9+10; int n,m; int a[maxn]; int dp[25][maxn]; int main() { //freopen("in.txt","r",stdin); int T;cin>>T; while(T--){ scanf("%d",&n); int sum=0; REP(i,1,n) scanf("%d",&a[i]),sum+=a[i]; scanf("%d",&m); MS0(dp); dp[0][0]=1; REP(i,1,n){ REP(j,0,sum){ if(j+a[i]<=sum) dp[i][j]+=dp[i-1][j+a[i]]; dp[i][j]+=dp[i-1][abs(j-a[i])]; dp[i][j]+=dp[i-1][j]; } } while(m--){ int k;scanf("%d",&k); puts(dp[n][k]?"YES":"NO"); } } return 0; }
C：dp，比赛的时候思路是对的，但开了n^3的内存直接超了，居然没能想到滚动数组。。
#include<iostream> #include<stdio.h> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #pragma comment(linker, "/STACK:102400000,102400000") #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=502; const int INF=1e9+10; const int MOD=5201314; int n; char ch[maxn][maxn]; int dp[2][maxn][maxn]; int dx1[]={0,0,-1,-1}; int dx2[]={0,1,0,1}; int main() { //freopen("in.txt","r",stdin); int T;cin>>T; while(T--){ scanf("%d",&n); memset(dp,-1,sizeof(dp)); REP(i,1,n){ scanf("%s",ch[i]+1); } MS0(dp); dp[1][1][n]=(ch[1][1]==ch[n][n]?1:0); REP(i,2,n){ memset(dp[i%2],0,sizeof(dp[i%2])); REP(x1,1,i){ int y1=i+1-x1; for(int x2=n;x2>=n+1-i;x2--){ int y2=n+1-(i+1-(n+1-x2)); if(x1>x2) break; if(ch[x1][y1]!=ch[x2][y2]) continue; REP(k,0,3){ int px1=x1+dx1[k]; int py1=(i-1)+1-px1; int px2=x2+dx2[k]; int py2=n+1-(i-(n+1-px2)); if(px1<1||py1<1||px2>n||py2>n) continue; dp[i%2][x1][x2]+=dp[(i+1)%2][px1][px2]; dp[i%2][x1][x2]%=MOD; } } } } int ans=0; REP(i,1,n) ans=(ans+dp[n%2][i][i])%MOD; printf("%d ",ans); } return 0; }
D：不会，待补。据说是cdq分治。
E：最小费用最大流。由于要求最小时间，且时间的计算方式类似罚时，比如如果只有4个顾客和1个店员，那么总时间就是t+2t+3t+4t，因此要将每个店员拆成n个点，拆成的第k个点到每个顾客的费用是k*t，大概如下图。。然后求下满流时的最小费用就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<vector> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100100; const int INF=1e9+10; struct Edge { int from,to,cap,flow,cost; }; struct MCMF { int n,m,s,t; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n) { this->n=n; REP(i,1,n) G[i].clear(); edges.clear(); } void addedge(int from,int to,int cap,int cost) { edges.push_back((Edge){from,to,cap,0,cost}); edges.push_back((Edge){to,from,0,0,-cost}); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool bellman_ford(int s,int t,int &flow,int &cost) { REP(i,1,n) d[i]=INF; MS0(inq); d[s]=0;inq[s]=1;p[s]=0;a[s]=INF; queue<int> q; q.push(s); while(!q.empty()){ int u=q.front();q.pop(); inq[u]=0; for(int i=0;i<G[u].size();i++){ Edge& e=edges[G[u][i]]; inq[u]=0; if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){ d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if(!inq[e.to]) q.push(e.to),inq[e.to]=1; } } } if(d[t]==INF) return 0; flow+=a[t]; cost+=d[t]*a[t]; int u=t; while(u!=s){ edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; u=edges[p[u]].from; } return 1; } int Mincost(int s,int t) { int flow=0,cost=0; while(bellman_ford(s,t,flow,cost)); return cost; } };MCMF F; int n,m; int ti[30][30]; int main() { freopen("in.txt","r",stdin); int T;cin>>T; while(T--){ scanf("%d%d",&m,&n); REP(i,1,n){ REP(j,1,m){ scanf("%d",&ti[i][j]); } } F.init(n+m*n+2); int s=n+m*n+1,t=n+m*n+2; REP(i,1,m){ REP(j,1,n){ int v=i*n+j; REP(u,1,n){ F.addedge(u,v,1,j*ti[u][i]); } F.addedge(v,t,1,0); } } REP(i,1,n) F.addedge(s,i,1,0); printf("%d ",F.Mincost(s,t)); } return 0; }
