这两天做完了2014年的noip提高。
因为以前看了SDSC2016时gty的课件，题目思路都知道了一点，做起来没多大困难。
100+100+75+100+100+70=545
里面水分好多，好多题都是提交几次WA后才过，并且基本没打对拍........
今年noip我要考这么高的分该多好！！！(然而别做梦了，一比赛就慌，打代码又慢ヾ(=ﾟ･ﾟ=)ﾉ喵♪)
【生活大爆炸版石头剪刀布】
太水了..........
注意看清那个图
#include<iostream>
#include<cstdio>
using namespace std;
const int N=;
int n,na,nb;
int a[N],b[N],jud[][];
int ga=,gb=; void set(int i,int j){ //i win j
jud[i][j]=;
jud[j][i]=;
}
void init(){
for(int i=;i<;i++) jud[i][i]=;
set(,);
set(,);
set(,);
set(,);
set(,);
set(,);
set(,);
set(,);
set(,);
set(,);
}
int main(){
cin>>n>>na>>nb;
for(int i=;i<na;i++)
cin>>a[i];
for(int i=;i<nb;i++)
cin>>b[i]; init();
for(int i=;i<n;i++){
int tmp=jud[a[i%na]][b[i%nb]];
if(tmp==) ga++;
else if(tmp==) gb++;
}
printf("%d %d",ga,gb);
}
【联合权值】
暴力：枚举点对中间那个店。(O(n^2) 菊花图)
//baoli
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
const int N=,MOD=; int n; struct node{
ll w;
vector<int> ch;
} g[N];
int cnt=;
void add(int u,int v){
g[u].ch.push_back(v);
g[v].ch.push_back(u);
} ll mx=-,ans=;
void sol(int u){
ll p=;
int sn=g[u].ch.size();
for(int i=;i<sn;i++)
for(int j=;j<sn;j++){
if(i==j) continue;
int ch1=g[u].ch[i],ch2=g[u].ch[j];
mx=max(mx,p=g[ch1].w*g[ch2].w);
ans+=p%MOD;
}
}
int main(){
//freopen("link.in","r",stdin);
//freopen("link.out","w",stdout); scanf("%d",&n);
int u,v,w;
for(int i=;i<=n-;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=;i<=n;i++){
scanf("%d",&w);
g[i].w=w;
} for(int i=;i<=n;i++) sol(i); cout<<mx<<" "<<ans%MOD;
//fclose(stdin);
//fclose(stdout);
return ;
}
正解：看了课件才想到
max：找相邻节点中权值最大的两个
sum：加法结合律....预处理相邻节点的和，[a*(sum-a)+b*(sum-b)+…]
注意（u,v）和（v,u）都要算
图的话，用vector就行了
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
const int N=,MOD=; int n; vector<int> e[N];
ll w[N];
ll sum[N]; ll mx=-,ans=;
void sol(int u){
int sn=e[u].size();
int mx1=-,mx2=-;
for(int i=;i<sn;i++){
if(mx1==- || w[e[u][i]]>w[e[u][mx1]]) mx1=i;
sum[u]=(sum[u]+w[e[u][i]])%MOD;
}
for(int i=;i<sn;i++){
if(i==mx1) continue;
if(mx2==- || w[e[u][i]]>w[e[u][mx2]]) mx2=i;
}
if(mx1!=- && mx2!=-)
mx=max(mx,w[e[u][mx1]]*w[e[u][mx2]]); ll tmp=;
for(int i=;i<sn;i++){
tmp=(tmp+w[e[u][i]]*(sum[u]-w[e[u][i]]+MOD)%MOD)%MOD;
}
ans=(ans+tmp)%MOD;
}
int main(){
//freopen("link.in","r",stdin);
//freopen("link.out","w",stdout);
int u,v,ww;
scanf("%d",&n);
for(int i=;i<=n-;i++){
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=;i<=n;i++){
scanf("%d",&ww);
w[i]=ww;
} for(int i=;i<=n;i++) sol(i);
cout<<mx<<" "<<ans%MOD;
//fclose(stdin);
//fclose(stdout);
return ;
}
【飞扬的小鸟】
我只会70%的状态转移方程，不知为什么多拿了5分ヾ(･ω･`｡)
f(i,j)--->到i,j位置的最少点击数
f(i,j)=min{f(i-1,j+Yi-1), f(i-1,j-Xi-1 *k)+k | Li-1<j-Xi-1 *k，j+Yi-1 <Hi-1}
特判j==m 从i-1的任何地方都可以
[tips]：预设Li=0，Hi=m+1，省好多麻烦
注意碰到地和管道就算死，他问你通过几个管道
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=,M=,INF=1e9;
int n,m,k, x,y,p,ll,hh;
int up[N],down[N],l[N],h[N], has[N];
int f[N][M];
int ans=INF;
void dp(){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
f[i][j]=INF; for(int i=;i<=n;i++)
for(int j=l[i]+;j<h[i];j++){
int &now=f[i][j];
if(j==m)
for(int z=h[i-]-;z>l[i-];z--){
if(z==m) now=min(now,f[i-][z]+);
else if((m-z)%up[i-]==) now=min(now,f[i-][z]+(m-z)/up[i-]);
else now=min(now,f[i-][z]+(m-z)/up[i-]+);
}
else{
if(j+down[i-]<h[i-]) now=min(now,f[i-][j+down[i-]]);
for(int k=;;k++){
if(j-up[i-]*k>l[i-]) now=min(now,f[i-][j-up[i-]*k]+k);
else break;
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++) h[i]=m+;
for(int i=;i<n;i++){
scanf("%d%d",&x,&y);
up[i]=x;
down[i]=y;
}
for(int i=;i<k;i++){
scanf("%d%d%d",&p,&ll,&hh);
l[p]=ll;
h[p]=hh;
has[p]=;
} dp();
for(int j=l[n]+;j<h[n];j++) ans=min(ans,f[n][j]);
if(ans==INF){
cout<<<<"\n";
int flag=;
for(int i=n-;i>=;i--){
for(int j=l[i]+;j<h[i];j++){
if(f[i][j]<INF) {
int tmp=;
for(int z=;z<=i;z++) tmp+=has[z];
cout<<tmp;
flag=;break;
}
}
if(flag) break;
}
}else{
cout<<<<"\n"<<ans;
} // cout<<"\n\n\n";
// for(int i=0;i<=n;i++) cout<<has[i]<<"\n";
// for(int i=0;i<=n;i++)
// for(int j=l[i]+1;j<h[i];j++){
// printf("%d %d %d\n",i,j,f[i][j]);
// } }
【无线网络发射器选址】
好水..................
数据范围这么小，我实在舍不得就用它练了练二维前缀和，结果WA好几次才过
注意方案数不能只从（x+d，y+d）枚举，可能丢解
以后别从0开始了做死
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=;
int d,n;
int g[N][N],s[N][N];
int x,y,k; void sss(){
s[][]=g[][];
for(int i=;i<N;i++) s[][i]=s[][i-]+g[][i],
s[i][]=s[i-][]+g[i][];
for(int i=;i<N;i++)
for(int j=;j<N;j++)
s[i][j]=s[i][j-]+s[i-][j]-s[i-][j-]+g[i][j];
} inline int sre(int x,int y){
if(x< ||y<) return ;
x= x>=N ? N- :x;
y= y>=N ? N- :y;
return s[x][y];
}
inline int get(int x1,int y1,int x2,int y2){
return sre(x2,y2)-sre(x2,y1-)-sre(x1-,y2)+sre(x1-,y1-);
} int cnt=,mx=-;
int main(){
scanf("%d%d",&d,&n);
for(int i=;i<n;i++){
scanf("%d%d%d",&x,&y,&k);
g[x][y]=k;
} sss(); for(int x=d;x+d<N;x++)
for(int y=d;y+d<N;y++)
mx=max(mx,get(x-d,y-d,x+d,y+d)); for(int x=;x<N;x++)
for(int y=;y<N;y++)
if(get(x-d,y-d,x+d,y+d)==mx) cnt++;//printf("%d %d\n",x,y),cnt++; cout<<cnt<<" "<<mx;
}
【寻找道路】
以前看过题解了，所以做法一下子回忆过来了
倒着搜一遍与终点连通的点
很像白书上那一道理想路径（Ideal Path），虽然我还没做那道题
注意是路径上所有点所指向的点
邻接表比较合适吧，我还见了一个反向图，用的f来区别，结果好乱●﹏●
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=,M=; struct edge{
int v,ne;
}e[M];
int n,m,x,y,s,t;
int h[N];
int cnt=;
void ins(int u,int v){
e[++cnt].v=v;
e[cnt].ne=h[u];
h[u]=cnt;
} edge ef[M];
int hf[N];
int cntf=;
void insf(int u,int v){
ef[++cntf].v=v;
ef[cntf].ne=hf[u];
hf[u]=cntf;
} bool vis[N],del[N];
void dfsf(int u){
vis[u]=true;
for(int i=hf[u];i;i=ef[i].ne){
int v=ef[i].v;
if(!vis[v])
dfsf(v);
}
} int d[N];
void bfs(int s){
memset(vis,,sizeof(vis));
memset(d,-,sizeof(d));
queue<int> q;
q.push(s);
d[s]=;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(del[v]||vis[v]) continue;
q.push(v);
vis[v]=;
d[v]=d[u]+;
if(v==t) break;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
ins(x,y);
insf(y,x);
}
scanf("%d%d",&s,&t); dfsf(t);
for(int u=;u<=n;u++)
if(!vis[u]){
del[N]=true;
for(int i=hf[u];i;i=ef[i].ne){
int v=ef[i].v;
del[v]=true;
}
} bfs(s); cout<<d[t];
}
【解方程】
坑人的一道。。。。。
30%小学生暴力
50%都说是高精，我也这么说了ヾ(ﾟ∀ﾟゞ)
70%................看了课件 %质数 啊 %%%
100%..............又看了课件 “如果我们模的数字是k。左边式子带入x和带入x+k是没有区别的。如果我们把质数k取得小一些，这样x就不用试1~m，而是试1~k。这样复杂度就变成 O(nkprime)，如果k取10^4左右就完全没有问题。”
试着做了下70%的，随手写了个欧拉筛法选几个素数（→_→），又写了个大整数取模和快速幂取模，结果WA了，目测快速幂取模写抽了（→_→）*2......闷闷不乐一会看看了黄学长的blog，咦好像可以预处理pre[m][j]--->m^j%prime，然后就爆内存了（→_→）*3。发现黄学长没用long long我也改int，然后把M改成70%M的规模，就拿了70分...ヘ(_ _ヘ)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=,L=,M=; int n,m;
char a[N][L];
int aint[N];
int mod[]={,,,,}; void getmod(char *a,int len,int x,int p){
int tmp=,flag=;
if(a[]=='-') flag=;
else tmp=a[]-''; for(int j=;j<len;j++)
tmp=(tmp*+a[j]-'')%p;
aint[x]=flag?-tmp:tmp;
} //long long powmod(long long a,int b,long long p){
// long long ans=1;
// for(;b;b>>=1,a=(a*a)%p)
// if(b&1) ans=(ans*a)%p;
// return ans;
//}
int pre[M][N];
bool vis[M];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%s",a[i]); for(int i=;i<;i++){
for(int x=;x<=n;x++) getmod(a[x],strlen(a[x]),x,mod[i]); for(int j=;j<=m;j++) pre[j][]=;
for(int j=;j<=m;j++)
for(int z=;z<=n;z++) pre[j][z]=(pre[j][z-]*j)%mod[i]; for(int j=;j<=m;j++){
long long ans=aint[];
for(int z=;z<=n;z++)
ans=(ans+aint[z]*pre[j][z])%mod[i];
if(ans!=) vis[j]=;
}
}
int num=;
for(int i=;i<=m;i++) if(vis[i]==) num++;
cout<<num<<"\n";
for(int i=;i<=m;i++) {
if(vis[i]==) printf("%d\n",i);
}
}
总结
做的水分太多了。。。。。。。。真实比赛恐怕一半的分数都很难吧。没办法在弱校比赛经验不足也没学长领着，只能自己摸索。想到前几个月去青岛比赛的经历就不堪回首（我的成语没用错吧，语文一直弱），一道题调的不太好结果心烦意乱后面基本胡乱打了，唉；
我做的题太少了，打代码也太慢，并且比赛策略几乎为0，就瞎看些理论知识，有什么用！争取在今年noip前让自己变强吧（学校太弱，平常只有周五晚自习可以去机房；我学习也太好，（其他人）不舍得停课，甚至连比赛前可能也不一定，唉~~o(>_<)o ~~）。