NOIP 2014

题目链接:https://vijos.org/p/category/2014

D1T1 生活大爆炸版 石头剪刀布

没想到noip还会出纯模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define N 205
#define rep(i,l,r) for(int i=l;i<=r;++i)
int n,na,nb;
int a[N],b[N];
const int w[5][5]={{0,-1,1,1,-1},{1,0,-1,1,-1},{-1,1,0,-1,1},{-1,-1,1,0,1},{1,1,-1,-1,0}};
int main()
{
while(scanf("%d%d%d",&n,&na,&nb)!=EOF)
{
rep(i,0,na-1) scanf("%d",a+i);
rep(i,0,nb-1) scanf("%d",b+i);
int ans1=0,ans2=0;
rep(i,0,n-1)
{
int x=a[i%na],y=b[i%nb];
if(w[x][y]>0) ++ans1;
else if(w[x][y]<0) ++ans2;
}
printf("%d %d\n",ans1,ans2);
}
}

D1T2 联合权值

dfs一下就统计出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
#define N 200010
#define rep(i,l,r) for(int i=l;i<=r;++i)
int e,head[N<<1],last[N<<1],p[N];
int deep[N];
int a[N];
int sum[N],md[N];
int ans1,ans2;
int n;
void add(int &x,int y)
{
(x+=y)>=mod && (x-=mod);
}
void addedge(int x,int y)
{
head[++e]=y;
last[e]=p[x];
p[x]=e;
}
void dfs(int x,int pre,int dep)
{
deep[x]=dep;
sum[x]=0;
md[x]=0;
int now=0,ss=0,mm=0;
int max1=0,max2=0;
for(int j=p[x];j;j=last[j])
{
int y=head[j];
if(y==pre) continue;
dfs(y,x,dep+1);
add(sum[x],a[y]);
add(now,a[y]*a[y]%mod);
add(ss,sum[y]);
md[x]=max(md[x],a[y]);
mm=max(mm,md[y]);
if(a[y]>=max1) max2=max1,max1=a[y];
else max2=max(max2,a[y]);
}
add(ans2,2*ss*a[x]%mod);
add(ans2,(sum[x]*sum[x]-now+mod)%mod);
ans1=max(ans1,mm*a[x]);
ans1=max(ans1,max1*max2);
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
e=0;
memset(p,0,sizeof(p));
memset(md,0,sizeof(md));
memset(sum,0,sizeof(sum));
rep(i,1,n-1)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
rep(i,1,n) scanf("%d",a+i);
ans1=0,ans2=0;
dfs(1,0,1);
printf("%d %d\n",ans1,ans2);
}
}

D1T3 飞扬的小鸟

这个dp有、东西,日常不会dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
#define N 10010
#define M 1010
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int INF=0x3f3f3f3f;
bool wall[N];
vector<int> now,las;
int n,m,q;
int a[N],b[N];
int l[N],r[N];
int main()
{
scanf("%d%d%d",&n,&m,&q);
rep(i,0,n-1)
{
scanf("%d%d",a+i,b+i);
l[i]=0;
r[i]=m+1;
}
l[n]=0;r[n]=m+1;
rep(i,1,q)
{
int x;
scanf("%d",&x);
scanf("%d%d",&l[x],&r[x]);
wall[x]=true;
}

now.resize(m+5);
las.resize(m+5);
rep(i,1,m) las[i]=0;
las[0]=INF;
int ans1=INF,ans2=0;
rep(i,1,n)
{
int x=a[i-1];
rep(j,0,m) now[j]=INF;
rep(j,x,m)
{
now[j]=min(now[j],las[j-x]+1);
now[j]=min(now[j],now[j-x]+1);
}
rep(j,m-x,m)
{
now[m]=min(now[m],las[j]+1);
now[m]=min(now[m],now[j]+1);
}
rep(j,l[i]+1,r[i]-1)
if(j+b[i-1]<=m)
now[j]=min(now[j],las[j+b[i-1]]);
rep(j,0,l[i]) now[j]=INF;
rep(j,r[i],m) now[j]=INF;
if(wall[i])
rep(j,l[i]+1,r[i]-1)
if(now[j]<INF)
{
++ans2;
break;
}
swap(now,las);
}
rep(j,1,m) ans1=min(ans1,las[j]);
if(ans1<INF)
{
puts("1");
printf("%d\n",ans1);
}
else
{
puts("0");
printf("%d\n",ans2);
}
}

D2T1 无线网络发射器选址

记前缀和,然后枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
int n,d;
int a[130][130];
int main()
{
scanf("%d",&d);
scanf("%d",&n);
rep(i,1,n)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
++x;++y;
a[x][y]+=c;
}
int ans1=0,ans2=0;
rep(i,1,129)
rep(j,1,129)
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
rep(i,1,129)
rep(j,1,129)
{
int x=min(129,i+d);
int y=min(129,j+d);
int xx=max(0,i-d-1);
int yy=max(0,j-d-1);
int now=a[x][y]-a[x][yy]-a[xx][y]+a[xx][yy];
if(now>ans2) ans1=1,ans2=now;
else if(now==ans2) ++ans1;
}
printf("%d %d\n",ans1,ans2);
}

D2T2 寻找道路

先在反图上从终点bfs,求出哪些点能到终点,然后从起点正着按题意bfs就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 10010
#define M 200010
vector<int> edge[N];
vector<int> redge[N];
queue<int> q;
bool vis[N];
bool ok[N];
int dis[N];
int n,m;
void pre(int s)
{
vis[s]=true;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(auto &y:redge[x])
if(!vis[y])
{
vis[y]=true;
q.push(y);
}
}
}
int bfs(int st,int ed)
{
if(!ok[st]) return -1;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q.push(st);
while(!q.empty())
{
int x=q.front();
q.pop();
for(auto &y:edge[x])
if(ok[y] && dis[y]==-1)
{
dis[y]=dis[x]+1;
q.push(y);
}
}
return dis[ed];
}
int main()
{
scanf("%d%d",&n,&m);
rep(i,1,m)
{
int x,y;
scanf("%d%d",&x,&y);
redge[y].push_back(x);
edge[x].push_back(y);
}
int st,ed;
scanf("%d%d",&st,&ed);
pre(ed);
memset(ok,true,sizeof(ok));
rep(y,1,n)
if(!vis[y])
for(auto &x:redge[y])
ok[x]=false;
printf("%d\n",bfs(st,ed));
}

D2T3 解方程

直接解肯定没办法,只能枚举答案,然后随机素数取模验证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 1000010
char s[105][10010];
int val[105][205];
int f[20000][10];
bool ok[N];
const int prime[]={19997,19961,19759,18013,17011,15359};
const int tot=6;
int n,m;

int calc(char *s,int mod)
{
int now=0;
for(int i=(s[0]=='-')?1:0;s[i];++i)
now=(1LL*now*10+s[i]-'0')%mod;
if(s[0]=='-') now=(mod-now)%mod;
return now;
}
int check(int x,int y,int mod)
{
int now=1,ans=0;
rep(i,0,n)
{
ans+=1LL*val[i][y]*now%mod;
if(ans>=mod) ans-=mod;
now=1LL*now*x%mod;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
rep(i,0,n)
{
scanf("%s",s[i]);
rep(j,0,tot-1) val[i][j]=calc(s[i],prime[j]);
}
rep(i,1,m) ok[i]=true;
int ans=0;
rep(i,0,m)
if(ok[i])
{
for(int j=0;j<tot;++j)
{
if(i<prime[j]) f[i][j]=check(i,j,prime[j]);
if(f[i%prime[j]][j]) ok[i]=false;
}
if(i>0 && ok[i]) ++ans;
}
printf("%d\n",ans);
rep(i,1,m) if(ok[i]) printf("%d\n",i);
}

NOIP 2014
https://izard.space/2018/09/28/NOIP-2014/
作者
forever_you
发布于
2018年9月28日
许可协议