昨天剛剛考完試然后就翹晚自習跟今天上午兩節課的語文和英語做做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\n%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\n%d",ans);
? ? ? ? ? ? ? ? ? ? return 0;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? printf("0\n0");
? ? }
}
day2t3：解方程
比較呵呵了，看一眼沒思路，嗯打樣例數據。一片WA聲想起。
看題解似乎是道數論的題目。去模……去***的。我數學拋物線還沒好好學，跟我扯這些。。。
然后Candy？跟我說這道模擬會拿30分，高精50分。好吧。早知道我就做做了。
總的來說，第一遍ac的總分=100+100+80+30+0+0=310分
考試認真一點就再加上方正心態把最后一問寫個模擬就可以 100+100+80+30+100+30=460分。
后悔也沒用了，吃一斬長一智。
)
)
 support enabled in your kernel...)
