第一次進入DIV1，果斷被虐，沒法下手。賽後先把DIV2解決了吧
A. System of Equations
問a*a+b=m a+b*b=n，的解a,b,有多少組，因為a,b都非負，而且m和n的范圍在1000以內，直接暴力，1000*1000即可
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 55
#define inf 1<<29
#define MOD 9973
#define Max 301
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
int cnt=0;
for(int i=0;i<=1000;i++)
for(int j=0;j<=1000;j++)
if(i*i+j==n&&j*j+i==m)
cnt++;
printf("%d\n",cnt);
}
return 0;
}
B. Hometask
由一些數字組成一個整數，能整除2，3，5，而且要最大的。
能同時整除2，5的，末位必然是0，能整除3的，所有位數和必為3的倍數。
首先判斷是否有0，如果沒有則輸出-1.
將所有數字降序排列（因為題目要求最大的整數）
接下來看所有位數和是否為3的倍數，如果是，按順序輸出。
接下來就可能會刪除某些數字，刪除一位肯定比刪除兩位要大，而且只可能刪除一位或者兩位。
如果數字和模3為1，則刪除一個盡可能小的，模3為1的數，for(int i=1;i<10;i+=3)，如果存在一個這樣的數，刪除
如果不存在，則接下來可能是刪除兩位的，而且刪除的兩位模3都為2，從小往大的找，刪除兩位
如果數字和模3為2，則刪除一個盡可能小的，模3為2的數，for(int i=2;i<10;i+=3)，如果存在一個這樣的數，刪除
如果不存在，則接下來可能是刪除兩位的，而且刪除的兩位模3都為1，從小往大的找，刪除兩位
如果上述情況都不存在，則輸出-1
在處理的時候，注意別輸出000000就行了，包括刪除之後的輸出。
代碼很shi，就不貼了
C. Game
DIV1的A題，還以為網絡流，一直在建圖，弱爆了。
可以發現1->2 2->3 3->1為1，其余為2，其實就是循環右移一位是1，兩位就是2。
加上一點小貪心，枚舉第一台機器，首先將能做的都做了，而且把接下來沒有限制的都加入隊列
如果這台機器沒有任務可做，則到下一台，時間+1，直到所有任務完成。也就是選了一台機子之後，先把能做的全都做了，避免轉移花費，而且在做了一個任務之後，要把其它沒有限制的加入隊列。
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 55
#define inf 1<<29
#define MOD 9973
#define Max 301
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
bool mat[205][205];
int c[205],n;
int slove(int s){
int deg[205];
memset(deg,0,sizeof(deg));
queue<int>que[3];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(mat[i][j])
deg[i]++;
if(deg[i]==0)
que[c[i]].push(i);
}
int ret=0,cnt=n;
bool flag[205];
memset(flag,true,sizeof(flag));
while(!que[0].empty()||!que[1].empty()||!que[2].empty()){
if(que[s].empty()) {s=(s+1)%3;ret++;continue;}
int u=que[s].front();
que[s].pop();
cnt--;
flag[u]=false;
for(int i=1;i<=n;i++){
if(mat[i][u]){
deg[i]--;
if(deg[i]==0&&flag[i])
que[c[i]].push(i);
}
}
if(cnt==0)
break;
}
return ret;
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
c[i]--;
}
for(int i=1;i<=n;i++){
int k,u;
scanf("%d",&k);
while(k--){
scanf("%d",&u);
mat[i][u]=true;
}
}
int ans=inf;
for(int i=0;i<3;i++)
ans=min(ans,slove(i)+n);
printf("%d\n",ans);
}
return 0;
}
D. Numbers
組合計數。由於不能出現前導0，我們倒序考慮。從9到0，dp[i][j]表示考慮了數字i，長度為j的種數。
然後枚舉當前數字取的位數，注意下限，在代碼中，表示j位，當前數字i取j-k個 。則之前的取k個，那麼就是dp[i+1][k]*c[j][k] 前者是上一輪的種數，後者表示從j個位置 中取出k個放之前的，那麼剩下的j-k位放當前數字。
注意數字0的情況要特殊點， 不能有前導0
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 305
#define inf 1<<29
#define MOD 1000000007
#define Max 301
#define LL __int64
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
LL dp[11][205],c[205][205];
int n,a[10];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<10;i++)
scanf("%d",&a[i]);
for(int i=0;i<=n;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
}
memset(dp,0,sizeof(dp));
dp[10][0]=1;
for(int i=9;i>=0;i--){
for(int j=n;j>=0;j--)
for(int k=j-a[i];k>=0;k--)
if(i) dp[i][j]=(dp[i][j]+dp[i+1][k]*c[j][k])%MOD;
else if(j&&k) dp[i][j]=(dp[i][j]+dp[i+1][k]*c[j-1][k-1])%MOD;
}
LL ans=0;
for(int i=0;i<=n;i++)
ans=(ans+dp[0][i])%MOD;
printf("%I64d\n",ans);
}
return 0;
}
E. Relay Race
NOIP 2008 傳紙條，單向很簡單，雙向的可以考慮成兩個人同時從（1，1）到（n，n）。那麼用四維的表示兩個人的位置就行了，但是這題N達到300，四維的不行。
由於兩個人同時在移動，所以x1+y1=x2+y2。那麼可以省去一維，我們還可以用dp[i][j][k]表示走了i步，兩個人分別是第j行，第k行，則第一個人在i-j+2列，第二個人在i-k+2列。
轉移的時候注意不要交叉，而且到達同一位置的時候不能多取。
可能為負，注意初始化
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 305
#define inf 1<<29
#define MOD 9973
#define Max 301
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
int dp[N<<1][N][N];
int a[N][N],n;
int way[4][2]={{0,0},{0,1},{1,0},{1,1}};
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(dp,0x81,sizeof(dp));
dp[0][1][1]=a[1][1];
for(int i=1;i<=2*n-2;i++)
for(int j=1;j<=i+1&&j<=n;j++)
for(int k=j;k<=i+1&&k<=n;k++){
for(int r=0;r<4;r++)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-way[r][0]][k-way[r][1]]);
dp[i][j][k]+=a[j][i-j+2]+a[k][i-k+2]-(j==k?a[k][i-k+2]:0);
}
printf("%d\n",dp[2*n-2][n][n]);
}
return 0;
