DQS DQS

NOIP2014解题报告

in 算法,NOIPread (179) 文章转载请注明来源!

作为复习和康复训练,先写了一遍NOIP2014。
发现了好多问题,包括我自己现在犯的错误(虽然有些错误当初学竞赛的时候早改了…),还有对这些老题的新理解。

这里就不再重复解题思路,只记录一些新的东西。题解请戳我的CSDN搜索。

生活大爆炸版石头剪刀布

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int SZ = 250;

int sts[SZ][SZ] =
{{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 a[SZ],b[SZ];

int main()
{
    int N,n,m;
    scanf("%d%d%d",&N,&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= m;i ++) scanf("%d",&b[i]);
    int ans1 = 0,ans2 = 0;
    while(N --)
    {
        static int i = 1,j = 1;
        ans1 += sts[a[i]][b[j]];
        ans2 += sts[b[j]][a[i]];
        i ++,j ++;
        if(i == n + 1) i = 1;
        if(j == m + 1) j = 1;
    }
    printf("%d %d",ans1,ans2);
    return 0;
}

联合权值

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;

const int SZ = 200010;
const int mod = 10007;

int val[SZ],a[SZ],b[SZ],s[SZ],maxn[SZ];
int sum = 0,maxx = 0;

void opt(int a,int b) // b gengxin a
{
    sum = (sum + s[a] * val[b] % mod) % mod;
    maxx = max(maxx,maxn[a] * val[b]);
    s[a] = (s[a] + val[b]) % mod;
    maxn[a] = max(maxn[a],val[b]);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n - 1;i ++) scanf("%d%d",&a[i],&b[i]);
    for(int i = 1;i <= n;i ++) scanf("%d",&val[i]);
    for(int i = 1;i <= n - 1;i ++)
    {
        int a = ::a[i],b = ::b[i];
        opt(a,b); opt(b,a);
    }
    printf("%d %d",maxx,sum * 2 % mod);
    return 0;
}

飞扬的小鸟

这个有必要说两句。
这个题本质就是向上跳是一个多重背包,向下落是可以丢弃一个物品。
对于每一步,只能选择向上跳N步(放物品)或者向下落一下(丢物品)。
也就是说每一步不能同时放和丢,也就是说向上和向下转移要分开写。

还有就是,我们发现多重背包需要在同一步中转移,也就是优化k次选择的做法,即同行转移。
此时的问题:因为我们转移完之后需要把不合法部分标记为INF,可是同行转移时有可能从不合法的位置转移过来,不会出错吗?
当然不会。
因为本质上还是从上一步转移过来的,只是用当前行来表示而已。比如说我们从j-d[i](跳了k-1次)转移到j(跳了k次),如果j-d[i]不合法而j合法,那么只能表示跳k-1次不合法,而跳k次是合法的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;

const int INF = 10010;
const int SZ = 10010;

int up[SZ],down[SZ],dp[SZ][1010];

struct pipes
{
    int l,r;
}l[SZ];


int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0;i < n;i ++)
        scanf("%d%d",&up[i],&down[i]);
    for (int i = 1;i <= n;i ++) l[i].l = 0,l[i].r = m + 1;
    for (int i = 1;i <= k;i ++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        l[a].l = b; l[a].r = c;
    }
    dp[0][0] = INF;
    for(int i = 1;i <= n;i ++)
        for(int j = 0;j <= m;j ++)
            dp[i][j] = INF;

    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            if(j - up[i - 1] >= 0)
                dp[i][j] = min(dp[i][j],dp[i - 1][j - up[i - 1]] + 1),
                dp[i][j] = min(dp[i][j],dp[i][j - up[i - 1]] + 1);
            if(j == m)
                for(int k = j - up[i - 1];k <= m;k ++)
                    dp[i][j] = min(dp[i][j],dp[i - 1][k] + 1),
                    dp[i][j] = min(dp[i][j],dp[i][k] + 1);
        }
        for(int j = 1;j <= m;j ++)
            if(j + down[i - 1] <= m)
                dp[i][j] = min(dp[i][j],dp[i - 1][j + down[i - 1]]);

        for(int j = 0;j <= l[i].l;j ++) dp[i][j] = INF;
        for(int j = l[i].r;j <= m;j ++) dp[i][j] = INF;
    }
    int ans1 = INF;
    for(int j = 1;j <= m;j ++)
        ans1 = min(ans1,dp[n][j]);
    if(ans1 < INF)
    {
        printf("1\n%d",ans1);
    }
    else
    {
        int ans2 = 0,pos;
        for(int i = 0;i < n;i ++)
        {
            bool flag = 0;
            for(int j = 1;j <= m;j ++)
                if(dp[i][j] < INF) flag = 1;
            if(!flag) { pos = i - 1; break; }
        }
        for(int i = 1;i <= pos;i ++)
            if(l[i].r != m + 1) ans2 ++;
        printf("0\n%d",ans2);
    }
    return 0;
}

无线网络发射器选址

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

int d,maps[200][200],n;

int check(int x,int y)
{
    int ans = 0;
    for(int i = x - d;i <= x + d;i ++)
        for(int j = y - d;j <= y + d;j ++)
            if(0 <= i && i <= 128 && 0 <= j && j <= 128)
                ans += maps[i][j];
    return ans;
}

int main()
{
    scanf("%d%d",&d,&n);
    for(int i = 1;i <= n;i ++)
    {
        int x,y,d;
        scanf("%d%d%d",&x,&y,&d);
        maps[x][y] = d;
    }
    int ans = 1,maxn = 0;
    for(int i = 0;i <= 128;i ++)
        for(int j = 0;j <= 128;j ++)
        {
            int tmp = check(i,j);
            if(maxn == tmp)
                ans ++;
            else if(maxn < tmp)
                ans = 1,maxn = tmp;
        }
    printf("%d %d",ans,maxn);
    return 0;
}

寻找道路

这个题当初代码写的不优美,是第二遍BFS时判断的,不过有效避免了我刚刚犯的错误2333
我现在写的是搜之前判断好,不过忘了判断起点是否合法了……

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 200010;


int head[SZ],nxt[SZ],to[SZ];
int tot = 1;

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

void init()
{
    tot = 1;
    memset(to,0,sizeof(to));
    memset(nxt,0,sizeof(nxt));
    memset(head,0,sizeof(head));
}

int ff[SZ],tt[SZ],tm[SZ];

queue<int> q;
bool vis[SZ];

void bfs1(int s)
{
    q.push(s); vis[s] = 1;
    while(q.size())
    {
        int u = q.front(); q.pop();
        for(int i = head[u];i;i = nxt[i])
        {
            int v = to[i]; tm[v] ++;
            if(!vis[v])
                vis[v] = 1,q.push(v);
        }
    }
}

bool use[SZ],path[SZ];
int dist[SZ];

int bfs2(int s,int t)
{
    q.push(s); use[s] = 1;
    dist[t] = -1;
    while(q.size())
    {
        int u = q.front(); q.pop();
        if(!path[u]) continue;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = to[i];
            if(path[v] && !use[v])
                use[v] = 1,q.push(v),dist[v] = dist[u] + 1;
        }
    }
    return dist[t];
}

int cd[SZ];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i ++)
        scanf("%d%d",&ff[i],&tt[i]);
    for(int i = 1;i <= m;i ++)
        build(tt[i],ff[i]);
    int s,t;
    scanf("%d%d",&s,&t);
    bfs1(t);
    init();
    for(int i = 1;i <= m;i ++)
        build(ff[i],tt[i]),cd[ff[i]] ++;
    for(int i = 1;i <= n;i ++)
        if(cd[i] == tm[i])
            path[i] = 1;
    printf("%d",bfs2(s,t));
    return 0;
}

解方程

现在审视这个题,感觉自己还是不喜欢这道题……
我当初给出的做法是选择小质数,然后枚举[1,p-1]的答案,在noip原数据弱的情况下顺利通过了。
但看看$a_i$的数据范围,我觉得把质数从小到大乘到刚好不超范围作为$a_i$,那样选小质数就没意义了,怎样都是0。
除去一些太小的质数,用大质数互相组合一下,于是这题就成RP题了……
所以我去bzoj该题讨论版复制了一份质数

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int SZ = 20010;
const int pri[] = {30011,11261,14843,19997,10007,21893};
char a[110][SZ];
int num[10][110],ans[1000010],n,m;
bool use[1000010];

int get_num(char a[],int mod)
{
    int ans = 0,flag = 0;
    if(a[0] == '-') flag = 1;
    int len = strlen(a);
    for(int i = a[0] == '-'? 1 : 0;i < len;i ++)
        ans = (ans * 10 % mod + a[i] - '0') % mod;
    return flag ? -ans + mod : ans;
}

bool check(int x,int id)
{
    int ans = num[id][n],mod = pri[id];
    for(int i = n - 1;i >= 0;i --)
        ans = ((LL)ans * x % mod + num[id][i]) % mod;
    //printf("%d %d\n",x,ans);
    return ans == 0;
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0;i <= n;i ++)
        scanf("%s",a[i]);
    for(int i = 0;i < 6;i ++)
        for(int j = 0;j <= n;j ++)
            num[i][j] = get_num(a[j],pri[i]);

    /*for(int i = 0;i < 6;i ++,puts(""))
        for(int j = 0;j <= n;j ++)
            printf("%d ",num[i][j]);*/

    for(int i = 0;i < 6;i ++)
        for(int j = 1;j < pri[i];j ++)
            if(!check(j,i))
                for(int k = j;k <= m;k += pri[i])
                    use[k] = 1;
    for(int i = 1;i <= m;i ++)
        if(!use[i])
            ans[++ ans[0]] = i;
    for(int i = 0;i <= ans[0];i ++)
        printf("%d\n",ans[i]);
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法NOIP
最后由DQS修改于2017-07-04 20:45
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆