首页 > 其他分享 >暑假集训CSP模拟一

暑假集训CSP模拟一

时间:2024-07-19 09:01:32浏览次数:13  
标签:return int max1 long 集训 else 暑假 now CSP

赛时rank 14 T1 0,T2 0,T3 100,T4 0

T1大模拟出题人_______

T1 Start

大模拟,注意细节。

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
#endif
using ll = long long;using ull = unsigned long long;
int n,m,k,now,nowp,sgn = 1;
struct node{
    string name;
    vector<string> nor,abnor;
    bool Double = false;
}a[40];
queue<string> Card;
inline bool is_normal(string s){return (s!="PASS"&&s!="DOUBLE"&&s!="TURN");}
inline void Print_Used(string name,string card){cout<<name+" used "+card+",now p="<<nowp<<".\n";}
inline void change_now(int &now,int delta){now += delta;if(now <= 0) now += n;if(now > n) now -= n;}
inline void get_new_card(int now){
    string s = Card.front();Card.pop();
    if(is_normal(s)) a[now].nor.push_back(s);
    else a[now].abnor.push_back(s);
}
inline bool del_double_by_solve(string aim){
    for(auto i = a[now].abnor.begin();i != a[now].abnor.end(); ++i)
        if((*i) == "") a[now].abnor.erase(i);
    for(auto i = a[now].abnor.begin();i != a[now].abnor.end();++i){
        if((*i) == aim){
            Print_Used(a[now].name,*i);
            a[now].abnor.erase(i);
            get_new_card(now);
            a[now].Double = false;
            return true;
        }
    }
    return false;
}
inline int get_order(char s){
    if(s == 'C') return 4;
    else if(s == 'A') return 3;
    else if(s == 'B') return 2;
    else if(s == 'D') return 1;
    else return 0;
}
inline int get_nxtp(int p,string s){
    int x = 0;
    for(int i = 1;i < s.size(); ++i) x = x*10+(s[i]-'0');
    if(s[0] == 'A') return p+x;
    else if(s[0] == 'B') return p-x;
    else if(s[0] == 'C') return p*x;
    else if(s[0] == 'D') return (int)(floor(1.0*p/x));
    else return x;
}
inline void Print_Lost(string name){cout<<name+" lost the game.\n";}
inline int Get_Order(char s){
    if(s == 'D') return 4;
    if(s == 'B') return 3;
    if(s == 'A') return 2;
    if(s == 'C') return 1;
    return 0;
}
inline void Work(){
    while(true){
        // for(auto i:a[now].nor) cout<<i<<' ';
        // cout<<' ';
        // for(auto i:a[now].abnor) cout<<i<<' ';
        if(a[now].Double){
            if(del_double_by_solve("PASS")) change_now(now,sgn),a[now].Double = true;
            else if(del_double_by_solve("TURN")) sgn = -sgn,change_now(now,sgn),a[now].Double = true;
            else if(del_double_by_solve("DOUBLE")) change_now(now,sgn),a[now].Double = true;
            else{
                pair<int,pair<string,vector<string>::iterator> > max1;
                max1.first = INT_MAX;
                for(auto i = a[now].nor.begin();i != a[now].nor.end();++i){
                    if((*i) == ""){continue;}
                    int emm = get_nxtp(nowp,*i);
                    if(emm < max1.first || (emm == max1.first && Get_Order(max1.second.first[0])<Get_Order((*i)[0])))
                        max1 = make_pair(emm,make_pair(*i,i));
                }
                if(max1.first > 99){
                    vector<string>().swap(a[now].abnor);
                    vector<string>().swap(a[now].nor);
                    for(int i = 1;i <= 3; ++i) get_new_card(now);
                    return Print_Lost(a[now].name),void();
                }
                else{ 
                    nowp = max1.first,
                    Print_Used(a[now].name,max1.second.first),
                    get_new_card(now),
                    a[now].nor.erase(max1.second.second);
                }
                a[now].Double = false;
                goto K;
            }
            continue;
        }
        else{
            K:;
            pair<int,pair<string,vector<string>::iterator> > max1;
            max1.first = INT_MIN;
            for(auto i = a[now].nor.begin();i != a[now].nor.end(); ++i){
                if((*i) == "") {continue;}
                int emm = get_nxtp(nowp,*i);
                if(emm > 99) continue;
                if(emm > max1.first || (emm == max1.first && get_order((*i)[0]) > get_order(max1.second.first[0])))
                    max1 = make_pair(emm,make_pair(*i,i));
            }
            if(max1.first != INT_MIN){
                nowp = max1.first;
                Print_Used(a[now].name,max1.second.first);
                a[now].nor.erase(max1.second.second);
                get_new_card(now);
                change_now(now,sgn*1);
            }
            else{
                if(del_double_by_solve("PASS")) change_now(now,sgn);
                else if(del_double_by_solve("TURN")) sgn = -sgn,change_now(now,sgn);
                else if(del_double_by_solve("DOUBLE")) change_now(now,sgn),a[now].Double = true;
                else{
                    vector<string>().swap(a[now].abnor);
                    vector<string>().swap(a[now].nor);
                    for(int i = 1;i <= 3; ++i) get_new_card(now);
                    return Print_Lost(a[now].name),void();
                }
            }
        }
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i = 1;i <= n; ++i){
        cin>>a[i].name;
        for(int j = 1;j <= 3; ++j){
            string s;cin>>s;
            if(is_normal(s)) a[i].nor.push_back(s);
            else a[i].abnor.push_back(s);
        }
    }
    for(int i = 1;i <= k; ++i){
        string s;cin>>s;Card.push(s);
    }
    now = 1;
    for(int i = 1;i <= m; ++i){
        cout<<"Round "<<i<<":\n";
        Work();
        for(int j = 1;j <= n; ++j) a[j].Double = false;
        nowp = 0;
        sgn = 1;
    }
}

T2 mine

递推,考虑当前位的贡献只与当前位,上一位,下一位有关

设\(f_{i,0/1/2}\)表示第\(i\)位的下一位没有/有雷,第\(i\)位是雷时的方案数

当前位是\(0\)时,\(f_{i,0}=f_{i-1,0}\)

当前位是\(1\)时,\(f_{i,0} = f_{i-1,2},f_{i,1}=f_{i-1,0}\)

当前位是\(2\)时,\(f_{i,0}=f_{i-1,2}\)

当前位是\(*\)时,\(f_{i,2}=f_{i-1,1}+f_{i-1,2}\)

当前位是\(?\)时,\(f_{i,2}=f_{i-1,1}+f_{i-1,2},f_{i,0}=f_{i,1}=f_{i-1,0}+f_{i-1,2}\)

答案为\(f_{n,0}+f_{n,2}\)

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
#endif
using ll = long long;using ull = unsigned long long;
const int N = 1e6 + 10 ,mod = 1e9 + 7;
char s[N];
int n,f[N][3];
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>(s+1);
    n = strlen(s+1);
    f[0][0] = f[0][1] = 1;
    for(int i = 1;i <= n; ++i){
        if(s[i] == '0') f[i][0] = f[i-1][0];
        if(s[i] == '1') f[i][0] = f[i-1][2],f[i][1] = f[i-1][0];
        if(s[i] == '2') f[i][1] = f[i-1][2];
        if(s[i] == '*') f[i][2] = (f[i-1][1]+f[i-1][2])%mod;
        if(s[i] == '?') f[i][2] = f[i-1][1] + f[i-1][2],f[i][0] = f[i][1] = (f[i-1][0]+f[i-1][2])%mod;
        f[i][0]%=mod;f[i][1]%=mod;f[i][2]%=mod;
    }
    cout<<(0ll+f[n][0]+f[n][2])%mod<<'\n';
}

T3 小凯的疑惑

当\(gcd(x,y)\ne -1\)时,直接输出-1

证明显然,假设当前有一个数\(c\),那么若有\(ax+by=c\),则一定有\(gcd(x,y)\mid c\),若\(gcd(x,y)\ne 1\),则一定可以找出无穷个数,使得\(gcd(x,y)\nmid c\)

由于数据非常小,我们可以直接\(O(n)\)水过……

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
#endif
long long LCM(int a,int b){
    return 1ll * a / __gcd(a,b) * b;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    int x,y;
    cin>>x>>y;
    if(x > y) swap(x,y);
    if(x == 1) return puts("0"),0;
    if(__gcd(x,y) != 1) return puts("-1"),0;
    long long lcm = LCM(x,y),a = 0;
    for(int i = 0;;++i){
        long long emm = 1ll * i * y;
        if(emm + x > lcm) break;
        a += (lcm-emm-x+1)/x+1;
    }
    cout<<lcm-x+2-a<<'\n';
}

but,正解还是有必要想的

考虑这个暴力的实质,是将给数轴上标出的东西减去。

image

暴力是枚举\(x+0y,x+1y,x+2y,\ldots\)

列出式子,化一下就有了\(\sum_{i=0}^{x-1}\left\lfloor\frac{iy}{x}\right\rfloor\)

化简,两边同时乘上x,再将向下取整化成mod的形式

得到\(x\sum_{i=0}^{x-1}\left\lfloor\frac{iy}{x}\right\rfloor=\sum_{i=0}^{x-1}iy-\sum_{i=0}^{x-1}(iy\mod x)\)

等差数列求和,就有\(\frac{\frac{x(x-1)y}{2}-\frac{x(x-1)}{2}}{x}\)

即\(\frac{(x-1)(y-1)}{2}\)

T4 春节十二响

简单的贪心,看代码

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
#endif
using ll = long long;using ull = unsigned long long;
const int N = 2e5 + 10;
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt,d[N],son[N];
inline void add(int u,int v){edge[++cnt] = {v,head[u]};head[u] = cnt;}
bitset<N> vis;
int n,a[N];
priority_queue<int> q[N];
ll ans = 0;
inline void Merge(int x,int y){
    priority_queue<int> p;
    while(q[y].size()){
        p.push(max(q[x].top(),q[y].top()));
        q[x].pop();q[y].pop();
    }
    while(p.size()) q[x].push(p.top()),p.pop();
}
void dfs1(int x){
    d[x] = 1;
    for(int i = head[x]; i;i = edge[i].next){
        int y = edge[i].to;
        dfs1(y);
        if(d[y] > d[son[x]]) son[x] = y;
        d[x] = max(d[x],d[y]+1);
    }
}
void dfs(int x){
    if(son[x]){
        dfs(son[x]);
        q[x].swap(q[son[x]]);
    }
    for(int i = head[x]; i;i = edge[i].next){
        int y = edge[i].to;
        if(y == son[x]) continue;
        dfs(y);
        Merge(x,y);
    }
    q[x].push(a[x]);
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    for(int i = 2,f;i <= n; ++i){
        cin>>f;
        add(f,i);
    }
    dfs1(1);
    dfs(1);
    while(q[1].size()) ans += q[1].top(),q[1].pop();
    cout<<ans<<'\n';
}

标签:return,int,max1,long,集训,else,暑假,now,CSP
From: https://www.cnblogs.com/hzoi-Cu/p/18309867

相关文章

  • 2022CSP答案+解析(附题目)
    一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)1.以下哪种功能没有涉及C++语言的面向对象特性支持:()。A.C++中调用printf函数B.C++中调用用户定义的类成员函数C.C++中构造一个class或structD.C++中构造来源于同一基类的多个派生类答......
  • 『模拟赛』暑假集训CSP提高模拟1
    Rank感冒了,同时心情极差,状态不好wwA.Start打磨你。T1放大模拟还是过于抽象了,开局劝退,遂倒序开题。赛时想复杂了一点,开了两个二维数组存牌,同时存double状态时也出了问题,还没有考虑负数的向下取整。我太蒻了改后虽然还是300多行,但是思路起码清晰了很多,改了几个小错就......
  • 暑假集训CSP提高模拟1
    暑假集训CSP提高模拟1唐完乐!T1Start大模拟,之前还做过。结果照样挂90pts细节较多,比较坑的是除法要向下取整,而/是向\(0\)取整。T2mine这\(DP\)已经简单到不能在简单了。设\(dp_{i,0/1/2}\)表示到第\(i\)位,\(0\)后面不放雷,\(1\)后面放雷,\(2\)自己是雷。......
  • 暑假集训CSP提高模拟1
    暑假集训CSP提高模拟1\(T1\)T2687.Start原题:luoguP7506「Wdsr-2.5」琪露诺的算数游戏大模拟。\(T2\)T807.mine原题:CF404DMinesweeper1D设\(f_{i,0/1/2/3/4}\)分别表示处理到第\(i\)位时,第\(i\)位为雷/第\(i\)位不为雷,第\(i-1,i+1\)位不为雷/第\(......
  • 【比赛】暑假集训CSP提高模拟1
    T1Start10Pts题面(较长)大模拟。点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintinf=INT_MAX;stringnm[10]={"","D","B","A","C","E","PASS","......
  • 2023HACSP-J补测
    都快忘了自己还打过这个比赛了,所以来补一下。完整题目在这里查看。Day0来到郑州,寻找考场。幸好提前来了,因为考场大门就5m宽(HA用不用这么穷啊喂,来JZYZ不好么),开车转了20min才找到。旅馆离考场很近,走路就能到。和zjyDALAO住隔壁,晚上去他那里写了一会题就去睡了。Day1早上......
  • 2024 暑假集训杂题选做
    目录写在前面CF1981DCF1992F写在最后写在前面我是飞物。CF1981D2400妈的好诡异的题场上拿到这题我都不知道我要干啥呃呃考虑到每个合数均为若干质数的乘积,则若构造方案中有合数,可以将合数替换为质数从而减少使用的权值的种类数,于是仅需考虑使用质数构造,则此时并不需要考虑具......
  • 【java计算机毕设】网上购书管理系统MySQL servlet JSP项目设计源代码 期末寒暑假作业
    目录1项目功能2项目介绍3项目地址1项目功能【java计算机毕设】网上购书管理系统MySQLservletJSP项目设计源代码期末寒暑假作业小组作业 2项目介绍系统功能:servlet网上购书管理系统包括管理员、用户两种角色。管理员功能包括订单管理(已处理,未处理),顾客管理(添......
  • 2024信友队蓝润暑期集训提高1班②Day6
    知识总结拓扑排序给定一个有向图,找到一个拓扑排序,使得图中所有顶点都在拓扑排序中出现,且任意两个相邻顶点间都有路径相连。算法:找到入度为0的顶点,加入拓扑排序序列。对于剩余的顶点,如果其入度为0,则加入拓扑排序序列;否则,将其所有入边的顶点的入度减1。重复步骤2,直到所......
  • 暑假Java自学每日进度总结1
    今日所学:一.常用的cmd命令:1>盘符:2>dir(显示当前文件所有目录)3>cd目录(打开该目录)4>cd..(回到上一目录)5>cd(回到当前盘符初始态)6>cls(清屏)7>exit(退出cmd命令界面)8>cd目录1\目录2...(打开多级目录)二.创建用cmd打开软件的快捷方式:使用环境变量:1>电脑2>属性3>高......