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
NOIP 2014
https://izard.space/2018/09/28/NOIP-2014/
作者
forever_you
发布于
2018年9月28日
许可协议