爆零Day……没什么想说的，我A题卡住了后来不小心查到题解了就没交，E和G都是水题可惜我全！部！W！A！在！Y！E！S！和！N！O！上！了！！！
嗨呀，这是最气的，J题辣鸡出题人，延续了中国人出题的半拉子英语水平不说，题意是完全没有交代清楚，全机房都在枚举题意做题……很明显我这个非洲血统写错了，改了两次也不对劲，就一肚子气去补之前的题了。讲道理我队友都在刷专题，我还在这里跟着大队伍刷找来的题，会的还是会，不会的没时间补，最后时间浪费在这些沙茶错误上，何必呢……何必呢……
A - ztr loves math(HDU 5675)
题意：出题人想知道任意一个N<=10^18是否能拆成N=x^2-y^2(x和y是正整数)
思路：N=(x-y)*(x+y)我一直觉得找到是否能拆成两个因数就可以了。实际上，N=1*N，如果N是奇数，令x=(N+1)/2，y=(N-1)/2即可；如果是4的倍数，同理，x-y=2,x+y=N/2也可以解出来一组正整数解。于是你只需要判断是不是1和4的倍数，就没了= =。（注意特判N==1和N==4） 我好菜啊.jpg
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int T;
long long n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%I64d",&n);
if(n==1||n==4){printf("False\n");continue;}
if(n%4==0)
{
printf("True\n");
}
else
{
if(n%2==0)
printf("False\n");
else
printf("True\n");
}
}
return 0;
}
B - CA Loves GCD(HDU 5656)
题意：有N个1<=num[i]<=1000的数，取任意个数个数字，成为一种方案，所取数字的gcd值为该方案的gcd值，问所有方案的gcd总和。
思路：trick点在于数很小，至于怎么用：dp数组记录任意选择几个数字最后gcd为1...1000分别有多少种方案。当时考场上以为跟多校第一场那道D差不多，结果就没想出来，原来这个更暴力……
//我们令dp[i][j]表示在前i个数中，选出若干个数使得它们的gcd为j的方案数，于是只需要枚举第i+1个数是否被选中来转移就可以了。
//令第i+1个数为v，当考虑dp[i][j]的时候，我们令$dp[i+1][j] += dp[i][j],dp[i+1][gcd(j,v)] += dp[i][j]。
//复杂度O(N*MaxV) MaxV 为出现过的数的最大值。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<iostream>
#define MOD 100000007
using namespace std;
int N,num[1010];
long long dp[1010][1010];
long long gcd(long long x,long long y){return y==0?x:gcd(y,x%y);}
int g[1010][1010];
int main()
{
for(int i=1;i<=1000;i++)
for(int j=1;j<=1000;j++)
{
g[i][j]=gcd(i,j);
}
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&num[i]);
}
memset(dp,0,sizeof(dp));
dp[1][num[1]]=1;
for(int i=2;i<=N;i++)
{
dp[i][num[i]]++;
for(int j=1;j<=1000;j++)
{
if(!dp[i-1][j])continue;
dp[i][j]+=dp[i-1][j];
dp[i][j]%=MOD;
dp[i][g[j][num[i]]]+=dp[i-1][j];
dp[i][g[j][num[i]]]%=MOD;
}
}
long long ans=0;
for(int i=1;i<=1000;i++)
{
if(!dp[N][i])continue;
ans+=(dp[N][i]*i);
ans%=MOD;
}
printf("%I64d\n",ans);
}
return 0;
}
C - King's Pilots(HDU 5644)
%%%gss http://c.ejq.me/oi/2014/01/17/bzoj3280/
注意：该题输入格式里忘记说明，N后面那个数字是K。这个题跟gss题解讲的有点区别在于第一天开始就有飞行员可以用。找到另一个官方题解似乎更舒服一些。
#include<fstream>
#include<cstring>
#include<vector>
#include<deque>
#include<cmath>
#include<iostream>
using namespace std;
const int SIZEN=501,INF=0x7FFFFFFF;
class EDGE
{
public:
int u,v,c,w;
};
int MAXFLOW,cost,S,T;
int N,pilots[210];
vector <EDGE> edge;//所有边
vector <int> p[SIZEN];//点对应的边的编号
void CLEAR()
{
edge.clear();
for(int i=0;i<SIZEN;i++)p[i].clear();
}
void Addedge(int u,int v,int c,int w)
{
edge.push_back((EDGE){u,v,c,w});
edge.push_back((EDGE){v,u,0,-w});
int tmp=edge.size()-2;
p[u].push_back(tmp);
p[v].push_back(tmp+1);
}
bool SPFA()
{
deque <int> q;
//spfa
bool boo[SIZEN]={0};
int i,j,d[SIZEN],father[SIZEN]={0};
for(i=0;i<=2*N+1;i++)d[i]=INF;
q.push_back(S);
d[S]=0;
boo[S]=1;
EDGE ed;
while(!q.empty())
{
j=q.front();
boo[j]=false;
q.pop_front();
for(i=0;i<p[j].size();i++)
{
ed=edge[p[j][i]];
if(ed.c)
if(d[ed.v]>d[j]+ed.w)
{
d[ed.v]=d[j]+ed.w;
father[ed.v]=p[j][i];//father[]记录所来的边
if(!boo[ed.v])
{
boo[ed.v]=1;
q.push_back(ed.v);
}
}
}
}
if(d[T]==INF)return false;//没有找到最短路
//找到一条路径后
//1.找流量
i=T;
int flow=INF;
while(i!=S)
{
flow=min(edge[father[i]].c,flow);
i=edge[father[i]].u;
}
//fo<<flow<<endl;
MAXFLOW+=flow;
cost+=flow*d[T];
//2.减流量
i=T;
int now;
while(i!=S)
{
now=father[i];
edge[now].c-=flow;
edge[now^1].c+=flow;
i=edge[now].u;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
int Tests;
cin>>Tests;
int begins,M,payment[5],rest[5],training_days,training_cost,all_needs;
while(Tests--)
{
CLEAR();
cin>>N>>begins;
all_needs=0;
for(int i=1;i<=N;i++)cin>>pilots[i];
for(int i=1;i<=N;i++)all_needs+=pilots[i];
cin>>M>>training_days>>training_cost;
for(int i=0;i<M;i++)
cin>>payment[i]>>rest[i];
S=0;
T=2*N+1;
Addedge(S,N+1,begins,0);//一开始有k个飞行员可用
for(int i=1;i<=N;i++)
{
if(i>=training_days)
Addedge(S,N+i,INF,training_cost);//新训练飞行员去使用
Addedge(S,i,pilots[i],0);
Addedge(N+i,T,pilots[i],0);
if(i<N)
{
Addedge(i,i+1,INF,0);
Addedge(N+i,N+i+1,INF,0);
}
}
for(int i=0;i<M;i++)
for(int j=1;j+rest[i]<=N;j++)
Addedge(j,N+j+rest[i],INF,payment[i]);
cost=0;
MAXFLOW=0;
while(SPFA());
if(MAXFLOW==all_needs)
cout<<cost<<endl;
else
cout<<"No solution"<<endl;
}
return 0;
}
（卧槽花式翻车……清理流量时把p[SIZEN]都清理了，RE第一次见到Access Violation……
E - jrMz and angles(HDU 5660)
题意：有两种正多边形，N边的和M边的，问你能不能拼成360°。
思路：内角为180*(N-2)/N，取a个N边的，b个M边的，方程为：a*180*(N-2)/N+b*180*(M-2)/M=360转换一下：a*(N-2)*M+b*(M-2)*N=2*M*N
由于所有的角度都是很大的，1到10边形，每个同种的最多用6次（N==6时），直接两层0-6循环枚举就好。
当初我就想到了这解法，可是WA那么多发我一直以为是自己推导有问题，考试完去补题时冷静一看：Yes打成YES，No打成NO了……GG
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main()
{
int T;
int n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
if(n>m)
{
n=n+m;
m=n-m;
n=n-m;
}
if(m<=2)
{
printf("NO\n");
continue;
}
if(n<=2)
{
if(m==3||m==4||m==6)
printf("YES\n");
else
printf("NO\n");
continue;
}
int a,b,c;
a=(n-2)*m;
b=n*(m-2);
c=2*n*m;
bool flag=false;
for(int x=0;x<=6;x++)
for(int y=0;y<=6;y++)
if(a*x+b*y==c)
flag=true;
if(!flag)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}
F - Reincarnation(HDU 4622)
待补：后缀自动机/哈希解法
G - Lucky(HDU 5665)
题意：一个数集，有没有幸运数，幸运数指无法被集合里的数字累加所得的最小的非负整数（集合里的同个数字可以使用多次）
思路：同个数字使用多次……只要有1就可以得到所有正整数，如果没有1那么得不到1；最小非负整数，所以再找有没有0就够了。
然后，我以为这题也有其它坑点所以我WA了，事后发现是——YES打成了NO，NO打成了YES
嗨呀这是最气的，由于先写的这个所以我E写成了YES和NO，而不是Yes和No，所以导致这些签到题我都WA了……爆零
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
int T,N,a;
bool zero,one;
int main()
{
scanf("%d",&T);
while(T--)
{
zero=false;
one=false;
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&a);
if(a==0)zero=true;
if(a==1)one=true;
}
if(zero&&one)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
H - CA Loves Math(HDU 5657)
%%%hjz大爷讲的我并没有听懂，回头补。
J - TIANKENG’s rice shop(HDU 4884)
题意：未知。
思路：枚举题意做题。虽然是模拟但太恶心了不想补了……主要是考虑某一次炒饭时滞留的顾客要第一个客户的同种类型能满足的都满足，然而开始炒以后来的并不能给他多炒。那么你如果第一个人要第一种，第二个人要第二种，第三个人要第一种，在三个人同时等候的时候，做第一个人做不满第三个要求的情况下，是尽可能多去做，做完晾着还是说做够第一个人的，再做第二个人的，再做第三个人的？……请出题人珍惜自己的题目描述。
代码：无。