昨天刚刚考完试然后就翘晚自习跟今天上午两节课的语文和英语做做noip2014的题目。然后去评测了一番。首先day1day2的t1基本都是模拟，一看就出思路那种，直接ac掉。代码如下
day1t1：#include<iostream>
#define maxn 209
using namespace std;
int map[5][5] =
{{0, 0, 1, 1, 0},
{1, 0, 0, 1, 0},
{0, 1, 0, 0, 1},
{0, 0, 1, 0, 1},
{1, 1, 0, 0, 0}};
int n,t1,t2;
int a[maxn], b[maxn];
int sum1,sum2;
int m1,m2;
int main()
{
cin>>n>>t1>>t2;
for(int i = 0; i < t1; i++)
cin>>a[i];
for(int i = 0; i < t2; i++)
cin>>b[i];
while(n--)
{
sum1+=map[a[m1]][b[m2]];
sum2+=map[b[m2]][a[m1]];
if((++m1) >= t1)
m1-=t1;
if((++m2) >= t2)
m2-=t2;
}
cout<<sum1<<" "<<sum2<<endl;
return 0;
}
用一个二维数组模拟这几种情况的得分。然后用思路论好了，比较简单。
day2t1：
这个题我真的非常怀疑是否为普及组的题，一个穷举模拟然后就过了。本以为要用贪心，我懒得找bug所以直接提交结果就过了。666mdzz。
代码：#include<iostream>
using namespace std;
int n,maxn,sum,d;
int x[22],y[22],s[22],f[130][130];
int main()
{
cin>>d>>n;
for (int i=0;i<n;i++)
cin>>x[i]>>y[i]>>s[i];
for (int i=0;i<129;i++)
for (int j=0;j<129;j++)
for (int k=0;k<n;k++)
if (x[k]>=i-d && x[k]<=i+d && y[k]>=j-d && y[k]<=j+d)
f[i][j]+=s[k];
for (int i=0;i<129;i++)
for (int j=0;j<129;j++)
if (f[i][j]>maxn)
maxn=f[i][j];
for (int i=0;i<129;i++)
for (int j=0;j<129;j++)
if (f[i][j]==maxn)
sum++;
cout<<sum<<" "<<maxn<<endl;
return 0;
}
day1t2：可以有点难度了，求联合全值，嗯，我看第一眼的时候是个图论的题，就是穷举点然后用几个算法优化一下，floyed应该能过3个点吧，dijstra能过7个吧。自己用笔算的复杂度。呵呵……。之后我就敲了dijstra代码然后硬生生的过了8个点。两个点tle。算了，不使spfa了，我就直接看题解了。结果发现这是一道大水题。水到无极限的数学题。妈的我就是大牛们口中的二逼青年。具体看题解-_-。然后找这他们的思路打了代码。嗯：卡时间了，一样的代码交了三次才ac。代码：
#include<iostream>
#define maxn 200001
using namespace std;
struct Edge
{
int first;
int next;
}edge[maxn];
long long s[maxn];
int w[maxn];
int max1[maxn],max2[maxn];
void sphdehanshu(int x,int &max1,int &max2)
{
if(x>max1){max2=max1;max1=x;}
else
if(x>max2) max2=x;
}
int n,sum1,sum2,first,next;
int main()
{
cin>>n;
for(int i=1;i<=n-1;i++) cin>>edge[i].first>>edge[i].next;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n-1;i++)
{
first=edge[i].first;
next=edge[i].next;
s[first]=s[first]+w[next];
s[next]=s[next]+w[first];
sphdehanshu(w[next],max1[first],max2[first]);
sphdehanshu(w[first],max1[next],max2[next]);
}
for(int i=1;i<=n;i++)
if(max1[i]*max2[i]>sum1)sum1=max1[i]*max2[i];
for(int i=1;i<=n-1;i++)
{
first=edge[i].first;
next=edge[i].next;
sum2=(sum2+(s[first]-w[next])*w[next] % 10007) % 10007;
sum2=(sum2+(s[next]-w[first])*w[first] % 10007) % 10007;
}
cout<<sum1<<" "<<sum2<<endl;
return 0;
}
day2t2：这个题就是道图论呗，先倒着搜一遍去掉无关点，然后在用堆优化的dijstra或者bfs找最短路好了。然后呢本以为会ac结果输出的时候把endl打在前面，导致一片WA声。改过来ac掉。
代码：#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m,x,y,s,t,sum,cnt;
int head[20010],nxt[500000],to[500000],dis[20010];
int nhead[20010],nnxt[500000],nto[500000],ans;
bool dvis[20010],fky[20010],vis[20010];
queue <int> dl,js;
void cr(int x,int y)
{
sum++;
nxt[sum] = head[x];
head[x] = sum;
to[sum] = y;
}
void ncr(int x,int y)
{
cnt++;
nnxt[cnt] = nhead[x];
nhead[x] = cnt;
nto[cnt] = y;
}
void dfs(int x)
{
for (int tp = nhead[x];tp;tp = nnxt[tp])
{
if (!dvis[nto[tp]])
{
dvis[nto[tp]] = true;
dfs(nto[tp]);
}
}
}
void ndfs(int x)
{
for (int tp = nhead[x];tp;tp = nnxt[tp])
{
if (!fky[nto[tp]])
{
fky[nto[tp]] = true;
ndfs(nto[tp]);
}
}
}
void bfs(int x)
{
dl.push(x);
js.push(0);
vis[x] = true;
while (!dl.empty())
{
if (dl.front() == t)
{
ans = js.front();
return;
}
for (int tp = head[dl.front()];tp;tp = nxt[tp])
{
if (!fky[to[tp]] && !vis[to[tp]])
{
dl.push(to[tp]);
js.push(js.front()+1);
vis[to[tp]] = true;
}
}
dl.pop();
js.pop();
}
}
int main()
{
cin>>n>>m;
for (int i = 1;i <= m;i++)
{
cin>>x>>y;
cr(x,y);
ncr(y,x);
}
cin>>s>>t;
dvis[t] = true;
dfs(t);
for (int i = 1;i <= n;i++)
{
if (!dvis[i]) ndfs(i);
}
bfs(s);
if (ans || s == t)
cout<<ans<<endl;
else
cout<<"-1"<<endl;
return 0;
}
day1t3：哦呵呵，直接模拟超时了，我感觉是这样的。于是写了个背包，嗯不错过了3个点。最后抄了题解把本题ac掉了。没想到它就是个背包题。早知道就认真写写了。
代码：#include <cstring>
#include <cstdio>
#include<iostream>
int n,m,k,i,j,s,u,v,ans;
int f[10002][1002];
int top[10002],bot[10002];
int up[10002],down[10002];
int min(int a,int b) {return(a<b?a:b);}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (i=0;i<n;++i)
scanf("%d%d",&up[i],&down[i]);
for (i=0;i<=n;++i) top[i]=m+1;
for (i=1;i<=k;++i)
{
scanf("%d%d%d",&s,&u,&v);
bot[s]=u;
top[s]=v;
}
memset(f,0x3f,sizeof(f));
for (i=1;i<=m;++i) f[0][i]=0;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
u=j-up[i-1];
if (u>bot[i-1] && u<top[i-1]) f[i][j]=min(f[i-1][u]+1,f[i][j]);
if (u>0) f[i][j]=min(f[i][u]+1,f[i][j]);
}
for (j=m;j>=m-up[i-1] && j>=1;--j)
{
f[i][m]=min(f[i][m],f[i][j]+1);
if (j>bot[i-1] && j<top[i-1]) f[i][m]=min(f[i-1][j]+1,f[i][m]);
}
for (j=bot[i]+1;j<top[i];++j)
{
u=j+down[i-1];
if (u>bot[i-1] && u<top[i-1])
f[i][j]=min(f[i-1][u],f[i][j]);
}
}
ans=0x3f3f3f3f;
for (i=bot[n]+1;i<top[n];++i) ans=min(ans,f[n][i]);
if (ans<0x3f3f3f3f) printf("1
%d",ans);
else
{
ans=k;
for (i=n-1;i>=0;--i)
{
if (top[i]<=m)
{
ans--;
for (j=bot[i]+1;j<top[i];++j)
if (f[i][j]<0x3f3f3f3f)
{
++ans;
printf("0
%d",ans);
return 0;
}
}
}
printf("0
0");
}
}
day2t3：解方程
比较呵呵了，看一眼没思路，嗯打样例数据。一片WA声想起。
看题解似乎是道数论的题目。去模……去***的。我数学抛物线还没好好学，跟我扯这些。。。
然后Candy？跟我说这道模拟会拿30分，高精50分。好吧。早知道我就做做了。
总的来说，第一遍ac的总分=100+100+80+30+0+0=310分
考试认真一点就再加上方正心态把最后一问写个模拟就可以 100+100+80+30+100+30=460分。
后悔也没用了，吃一斩长一智。