常州集训Day3！

Posted on By 王子晔, 王子晔 常州集训Day3！无评论

提高组模拟试题 1

A.赌徒 (gambler)

结论题

这道题其实在样例数据就已经给我们提示了
就是题面上有三个特征，每一个特征都跟奇偶性有关，所以从奇偶性入手是最方便的。

  • 假设我们第一次翻了q个橙色硬币，k-q个蓝色硬币（0<=q<=m）。则这轮后有n-k+2q枚蓝色
    硬币，m+k-2q枚橙色硬币。
  • 若m是偶数，只需取q=m/2，这轮后就剩余k枚橙色硬币。下一轮一次翻完即可。
  • 若m是奇数，则k也是奇数，剩余橙色硬币数为偶数。直接令q=m，剩余
    枚硬币，这样我们就将这种情况化归到了上一种情况。同样艾佛必胜。
    综上艾佛必胜。
    这是一道数论题，我也是成功打出来了:laughing:
    但是我忘记对k=0的情况进行特判了！并且写n+m<=k时的等于号也弄丢了！导致我只有七十六分。。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=1;char c;
    do c=getchar();
    while(!isdigit(c)&&c!=&#039;-&#039;);
    if(c==&#039;-&#039;) 
    {
        f=-1,c=getchar();
    }
    while(isdigit(c)) 
    ｛
        x=x*10+c-&#039;0&#039;；
        c=getchar();
    ｝
    return x*f; 
}
int main()
{
    freopen("gambler.in","r",stdin);
    freopen("gambler.out","w",stdout);
    ll Test=read(),T=read();
    while(T--)
    {
        ll n=read(),m=read(),k=read();
        if(k==0||m==0||m%k==0)
        {
            cout<<"Ivor"<<endl;
            continue;
        }
        if(n+m<=k)
        {
            cout<<"Harper"<<endl;
            continue;
        }
        if((n&1)==((n+m)&1))
        {
            cout<<"Ivor"<<endl;
        }
        else
        {
            if(k&1) 
            {
                cout<<"Ivor"<<endl;
            }
            else
            {
                cout<<"Harper"<<endl;
            }
        }
    }
    return 0;
}

B.残片 (garbage)

这道题说真的，打题的时候已经有想到用字典树去打了，但是真的不知道怎么打，所以就没有提交
正确思路：

  • 具体实现时，还是枚举每个字符串，但在匹配不一样的字符时，我们遍历字典树中该串的对应路径，并在每一层枚举不同的字符。之后同样暴力建图，判环即可。
  • 而情况 (1) 中的前缀存在问题也是字典树的经典应用，可以顺带完成。

C.护手 (gauntlet)

求贡献 树状数组实现 链式前向星计算
树状数组昨天刚讲，今天不会用啊
考试的时候因为要求正奇数次和正偶数次的数的
异或和，所以就选择手打一串暴力，成功拿了25分 在看数据范围时已经算到了

错误代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e4+100;
int a[N],b[N],h[N],yin[N];
map<int,int> ma;
inline ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<&#039;0&#039; || c>&#039;9&#039;)
    {
        if(c==&#039;-&#039;)
        {
            f=-1;
        }   
        c=getchar();
    }
    while(c>=&#039;0&#039; && c<=&#039;9&#039;)
    {
        x=x*10+c-&#039;0&#039;;
        c=getchar();
    }
    return x*f;
}
int main()
{
    freopen("gauntlet.in","r",stdin);
    freopen("gauntlet.out","w",stdout);
    int sub=read();
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        ma[a[i]]=i;
    }
    yin[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        yin[i]=yin[i-1]^a[i];
    }
    for(int i=1;i<=m;i++)
    {
        memset(h,0,sizeof(h));
        int l=read(),r=read(),T=read(),y=(yin[l-1]==0?yin[r]:yin[l-1]^yin[r]);
        if(T)
        {
            int sum=0;
            for(int j=l;j<=r;j++)
            {
                int ip=lower_bound(b+1,b+n+1,a[j])-b;
                if(h[ip])
                {
                    sum=(sum==0?a[j]:sum^a[j]);
                }
                else{
                    h[ip]=1;
                }
            }
            cout<<sum<<endl;
        }
        else
        {
            cout<<y<<endl;
        }
    }
    return 0;
}

D.无量 (gazillion)

动态规划，二分找答案
真的知道用DP，但就是不会啊
考试的时候选择用深搜去暴力，稍微进行了一点优化，成功拿了35分。

正确思路：

全程没有用到任何高级的优化，却足以卡住很多人。
一切尝试都是为了优化程序时间复杂度而出发，将记忆化、重新设计状态、降维、倍增、二分等常
见的降低时、空复杂度的方法有机结合。

错误代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=110;
int c[N],p[N];
struct edge{
    int to,w;
};
vector<edge> v[N];
int rem[45][2025][1010];
int n,m,C,t;
int ans=-1;
void dfs(int u,int q,int l,int x,int d)
{
    if(n<=40&&q<=40*40&&x<=1010)
    {
        if(rem[u][q][x]>=l)
        {
            return ;
        }
        rem[u][q][x]=l;
    }
    if(l>=d)
    {
        ans=max(ans,q);
        return ;
    }
    if(x<1)
    {
        return ;
    }   
    for(int i=0;i<v[u].size();i++)
    {
        int to=v[u][i].to,w=v[u][i].w;
        if(q>=p[to]&&x-1<c[to])
        {
            dfs(to,q-p[to],l+w,min(c[to],C),d);
        }
        dfs(to,q,l+w,x-1,d);
    }
}
inline ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<&#039;0&#039;|| c>&#039;9&#039;)
    {
        if(c==&#039;-&#039;)
        {
            f=-1;
        }   
        c=getchar();
    }
    while(c>=&#039;0&#039; && c<=&#039;9&#039;)
    {
        x=x*10+c-&#039;0&#039;;
        c=getchar();
    }
    return x*f;
}
int main()
{
    freopen("gazillion.in","r",stdin);
    freopen("gazillion.out","w",stdout);
     n=read(),m=read(),C=read(),t=read();
    for(int i=1;i<=n;i++)
    {
        p[i]=read();
        c[i]=read();
    }
    for(int i=1;i<=m;i++)
    {
        int u=read(),to=read(),l=read();
        v[u].push_back({to,l});
    }
    for(int i=1;i<=t;i++)
    {
        memset(rem,0,sizeof(rem));
        ans=-1;
        int s=read(),q=read(),d=read();
        dfs(s,q-p[s],0,c[s],d);
        cout<<ans<<endl;
    }
    return 0;
}

总结

今天的难度还是挺高的，总过得了76+0+25+35=136分，还算不错吧。

训练日志

发表回复