首页 > 其他分享 >The 2022 ICPC Asia Xian Regional Contest

The 2022 ICPC Asia Xian Regional Contest

时间：2023-08-27 19:22:04浏览次数：45  
标签：Contest int Regional Xian long while pragma inline define

链接

C.Clone Ranran

题意：一个人要准备一场比赛，需要出c道题，他现在可以选择两种操作：1.花费a分钟自我复制一次。（复制的自己也可以接着复制）2.花费b分钟出一道题。问最短要多少分钟可以准备c道题。

思路：枚举自我复制的次数，挨个判断就行。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rg register
#define maxn 425450
#define P 131
#define int long long
#define INF 0X7F7F7F
#pragma GCC optimize(3)
#pragma -fcrossjumping
#pragma -fdefer-pop
#pragma -fmerge-constans
#pragma -fthread-jumps
#pragma -floop-optimize
#pragma -fif-conversion
#pragma -fif-conversion2
#pragma -fdelayed-branch
#pragma -fguess-branch-probability
#pragma -fcprop-registers
#pragma -fforce-mem
#pragma -foptimize-sibling-calls
#pragma -fstrength-reduce
#pragma -fgcse
#pragma -fcse-follow-jumps
#pragma -frerun-cse-after-loop
#pragma -fdelete-null-pointer-checks
#pragma -fextensive-optimizations
#pragma -fregmove
#pragma -fschedule-insns
#pragma -fsched-interblock
#pragma -fcaller-saves
#pragma -fpeephole2
#pragma -freorder-blocks
#pragma -fstrict-aliasing
#pragma -funit-at-a-time
#pragma -falign-functions
#pragma -fcrossjumping
#pragma -finline-functions
#pragma -fweb
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    } 
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline mul(int a,int b)
{
    int sum=1;
    while(b)
    {
        if(b&1) sum=sum*a;
        a=a*a;
        b>>=1;
    }
    return sum;
}
int t,a,b,c;
signed main()
{
    t=read();
    while(t--)
    {
        a=read(),b=read(),c=read();
        int ans=1e9+5;
        for(rg int i=0;;++i)
        {
            int num=mul(2,i);
            ans=min(ans,a*i+(int)ceil((double)c*1.0/(double)num*1.0)*b);
            if(num>=c) 
            {
                cout<<min(ans,i*a+b)<<endl;
                break;
            }
        }
    }
}
View Code

E. Find Maximum

题意：给你一个函数 f(x)，同时给t组询问，每次询问给出一个范围[l,r]，求这个范围中最大的 f(x)。

思路：将整数变成三进制形式观察，我们可以发现对于任意一个三进制形式的数，它的f(x)的值等于它各个位置上的数之和+它本身的长度。因此靠着这个性质可以采用贪心的思路来做。要想f(x)尽可能大，第一是需要数本身够长，第二就是需要各个位置上的2尽可能得多，因此可以枚举2的数量来进行判断。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rg register
#define maxn 125450
#define P 131
#define int long long
//#define int __int128
#define INF 0X7F7F7F
#pragma GCC optimize(3)
#pragma -fcrossjumping
#pragma -fdefer-pop
#pragma -fmerge-constans
#pragma -fthread-jumps
#pragma -floop-optimize
#pragma -fif-conversion
#pragma -fif-conversion2
#pragma -fdelayed-branch
#pragma -fguess-branch-probability
#pragma -fcprop-registers
#pragma -fforce-mem
#pragma -foptimize-sibling-calls
#pragma -fstrength-reduce
#pragma -fgcse
#pragma -fcse-follow-jumps
#pragma -frerun-cse-after-loop
#pragma -fdelete-null-pointer-checks
#pragma -fextensive-optimizations
#pragma -fregmove
#pragma -fschedule-insns
#pragma -fsched-interblock
#pragma -fcaller-saves
#pragma -fpeephole2
#pragma -freorder-blocks
#pragma -fstrict-aliasing
#pragma -funit-at-a-time
#pragma -falign-functions
#pragma -fcrossjumping
#pragma -finline-functions
#pragma -fweb
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    } 
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline mul(int a,int b)
{
    int sum=1;
    while(b)
    {
        if(b&1) sum=sum*a;
        a=a*a;
        b>>=1;
    }
    return sum;
}
inline int f(int x)
{
    if(x==0) return 1;
    else if(x%3==0) return f(x/3)+1;
    else return f(x-1)+1;
} 
inline int get(int temp,int num)
{
    int tot=0;
    while(num!=0)
    {
        tot=0;
        while(temp%3!=0) 
        {
            ++tot;
            temp--;
        }
        temp/=3;
        --num;
    }
    tot=0;
    while(temp%3!=0) 
    {
        ++tot;
        temp--;
    }
    return tot;
}
int t,l,r;
inline void work(int temp)
{
    int ans=max(f(l),f(r));
    vector<int>v;
    while(temp)
    {
        v.push_back(temp%3);
        temp/=3;
    }
    reverse(v.begin(),v.end());
    for(rg int i=0;i<v.size();++i)
    {
        if(v[i]==0) continue;
        temp=0;
        for(rg int j=0;j<=i;++j) temp=temp*3+v[j];
        temp--;
        for(rg int j=i+1;j<v.size();++j) temp=temp*3+2;
        if(temp>=l&&temp<=r) ans=max(ans,f(temp));
    }
    cout<<ans<<endl;
}
signed main()
{
    t=read();
    while(t--)
    {
        l=read(),r=read();
        work(r);
    }
}
View Code

F. Hotel

题意：签到题，需要考虑的点主要是有可能单人房比双人间还贵，所以三个人可以开三个双人间这种。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rg register
#define maxn 545
#define P 131
#define int long long
#define INF 0X7F7F7F
#pragma GCC optimize(3)
#pragma -fcrossjumping
#pragma -fdefer-pop
#pragma -fmerge-constans
#pragma -fthread-jumps
#pragma -floop-optimize
#pragma -fif-conversion
#pragma -fif-conversion2
#pragma -fdelayed-branch
#pragma -fguess-branch-probability
#pragma -fcprop-registers
#pragma -fforce-mem
#pragma -foptimize-sibling-calls
#pragma -fstrength-reduce
#pragma -fgcse
#pragma -fcse-follow-jumps
#pragma -frerun-cse-after-loop
#pragma -fdelete-null-pointer-checks
#pragma -fextensive-optimizations
#pragma -fregmove
#pragma -fschedule-insns
#pragma -fsched-interblock
#pragma -fcaller-saves
#pragma -fpeephole2
#pragma -freorder-blocks
#pragma -fstrict-aliasing
#pragma -funit-at-a-time
#pragma -falign-functions
#pragma -fcrossjumping
#pragma -finline-functions
#pragma -fweb
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    } 
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n;
int cost1,cost2,ans;//单人 双人 
signed main()
{
    n=read();
    cost1=read(),cost2=read();
    for(rg int i=1;i<=n;++i)
    {
        string s;
        cin>>s;
        int num1=1,num2=0,num3=0;
        if(s[1]==s[0]) num1++;
        else num2++;
        if(s[2]==s[0]) num1++;
        else if(s[2]==s[1]) num2++;
        else num3++;
        if(num1==1) ans+=min(cost1,cost2);
        else if(num1==2) ans+=min(2*cost1,cost2);
        else if(num1==3) ans+=min(3*cost1,min(2*cost2,cost2+cost1));
        if(num2==1) ans+=min(cost1,cost2);
        else if(num2==2) ans+=min(2*cost1,cost2);
        if(num3==1) ans+=min(cost1,cost2);
    }
    cout<<ans;
}
View Code

G. Perfect Word

题意：给你n个字符串。然后让你构建一个尽可能长的字符串，满足这个字符串的所有子串均在这n个字符串中出现过，输出这个字符串的长度。

思路：毫无疑问，需要构建的这个字符串一定是给定的这n个字符串中较长的某一个。因此对于其中一个符合答案的较长字符串i而言，n个字符串中所有比它短的字符串可以组成它的所有子串集。因此我们可以将字符串按长度从小到大排序，同时用哈希来加速判断。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rg register
#define maxn 125450
#define P 131
#define int long long
#define INF 0X7F7F7F
#pragma GCC optimize(3)
#pragma -fcrossjumping
#pragma -fdefer-pop
#pragma -fmerge-constans
#pragma -fthread-jumps
#pragma -floop-optimize
#pragma -fif-conversion
#pragma -fif-conversion2
#pragma -fdelayed-branch
#pragma -fguess-branch-probability
#pragma -fcprop-registers
#pragma -fforce-mem
#pragma -foptimize-sibling-calls
#pragma -fstrength-reduce
#pragma -fgcse
#pragma -fcse-follow-jumps
#pragma -frerun-cse-after-loop
#pragma -fdelete-null-pointer-checks
#pragma -fextensive-optimizations
#pragma -fregmove
#pragma -fschedule-insns
#pragma -fsched-interblock
#pragma -fcaller-saves
#pragma -fpeephole2
#pragma -freorder-blocks
#pragma -fstrict-aliasing
#pragma -funit-at-a-time
#pragma -falign-functions
#pragma -fcrossjumping
#pragma -finline-functions
#pragma -fweb
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    } 
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline mul(int a,int b)
{
    int sum=1;
    while(b)
    {
        if(b&1) sum=sum*a;
        a=a*a;
        b>>=1;
    }
    return sum;
}
int n;
struct node
{
    int len;
    string str;
}s[maxn];
inline bool cmp(node a,node b)
{
    return a.len<b.len;
}
unsigned long long p[maxn],h[maxn];
inline void Hash(string s)
{
    h[0]=s[0],p[0]=1;
    for(rg int i=1;i<s.length();++i)
    {
        h[i]=h[i-1]*P+s[i];
        p[i]=p[i-1]*P;
    }
    return ;
}
inline unsigned long long get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
map<int,int>mp;
int ans;
signed main()
{
    n=read();
    for(rg int i=1;i<=n;++i)
    {
        cin>>s[i].str;
        s[i].len=s[i].str.length();
    }
    sort(s+1,s+1+n,cmp);
    for(rg int i=1;i<=n;++i)
    {
        Hash(s[i].str);
        int sum=get(0,s[i].len-1);
        mp[sum]=1;
        bool flag=true;
        for(rg int j=0;j<s[i].len;++j)
        {
            for(rg int k=0;k<s[i].len-j;++k)
            {
                if(mp[get(k,k+j)]!=1) 
                {
                    flag=false;
                    goto outer;
                }
            }
        }
        outer:;
        if(flag==true) ans=max(ans,s[i].len);
    }
    cout<<ans;
}
View Code

J. Strange Sum

题意：给定一个长度为n的序列a。我们可以里面选择至多两个元素，当我们选择ai的时候，下一个元素必须在长度为i的区间里面选择（该区间需包含ai）。求所选的最大元素和。（可以不选）

思路：签到题，枚举第一个选择的元素，第二个就是求区间最大。这里我用的ST表。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rg register
#define maxn 425450
#define P 131
#define int long long
#define INF 0X7F7F7F
#pragma GCC optimize(3)
#pragma -fcrossjumping
#pragma -fdefer-pop
#pragma -fmerge-constans
#pragma -fthread-jumps
#pragma -floop-optimize
#pragma -fif-conversion
#pragma -fif-conversion2
#pragma -fdelayed-branch
#pragma -fguess-branch-probability
#pragma -fcprop-registers
#pragma -fforce-mem
#pragma -foptimize-sibling-calls
#pragma -fstrength-reduce
#pragma -fgcse
#pragma -fcse-follow-jumps
#pragma -frerun-cse-after-loop
#pragma -fdelete-null-pointer-checks
#pragma -fextensive-optimizations
#pragma -fregmove
#pragma -fschedule-insns
#pragma -fsched-interblock
#pragma -fcaller-saves
#pragma -fpeephole2
#pragma -freorder-blocks
#pragma -fstrict-aliasing
#pragma -funit-at-a-time
#pragma -falign-functions
#pragma -fcrossjumping
#pragma -finline-functions
#pragma -fweb
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    } 
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,a[maxn],ans;
int f[maxn][20];
int lg[maxn];
inline void ST_prework()
{
    for(rg int j=1;(1<<j)<=n;++j)
    {
        for(rg int i=1;i<=n-(1<<j)+1;++i)
        {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
inline int query(int l,int r)
{
    int k=lg[r-l+1]/(lg[2]);
    return max(f[l][k],f[r-(1<<k)+1][k]);
} 
signed main()
{
    n=read();
    for(rg int i=1;i<=n;++i) 
    {
        a[i]=read();
        f[i][0]=a[i];
    }
    lg[1]=0,lg[2]=1;
    for(rg int i=3;i<=n+5;++i) lg[i]=lg[i/2]+1;
    ST_prework();
    for(rg int i=1;i<=n;++i)
    {
        int temp=0;
        if(a[i]<=0) continue;
        int l=1,r=min(n,2*i-1);
        if(l<=i-1) temp=max(temp,query(l,i-1));
        if(r>=i+1) temp=max(temp,query(i+1,r));
        ans=max(ans,temp+a[i]);
    }
    cout<<ans;
}
View Code

L. Tree

题意：给你一棵树，需要你把其中所有的节点分成多个集合。集合一共有两类，第一类集合是该集合中的任意两个点满足祖先关系、第二类集合则相反，任意两个点都不满足祖先关系。求最少能分成多少个集合。

思路：可以想象得到，第一类集合大概是长的类似一条链一样的。第二类集合则是多个没关系的叶子节点所组成的。因此，第一类集合和链长有关系，而第二类集合和叶子节点深度有关系。因此我们可以采用长链剖分，将整棵树给分成一条条链，然后将链按长度从大到小进行排序。接着枚举i，前i条链上的所有节点则采用 第一类集合，后面的节点则采用第二类集合。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rg register
#define maxn 2025450
#define P 131
#define int long long
#define INF 0X7F7F7F
#pragma GCC optimize(3)
#pragma -fcrossjumping
#pragma -fdefer-pop
#pragma -fmerge-constans
#pragma -fthread-jumps
#pragma -floop-optimize
#pragma -fif-conversion
#pragma -fif-conversion2
#pragma -fdelayed-branch
#pragma -fguess-branch-probability
#pragma -fcprop-registers
#pragma -fforce-mem
#pragma -foptimize-sibling-calls
#pragma -fstrength-reduce
#pragma -fgcse
#pragma -fcse-follow-jumps
#pragma -frerun-cse-after-loop
#pragma -fdelete-null-pointer-checks
#pragma -fextensive-optimizations
#pragma -fregmove
#pragma -fschedule-insns
#pragma -fsched-interblock
#pragma -fcaller-saves
#pragma -fpeephole2
#pragma -freorder-blocks
#pragma -fstrict-aliasing
#pragma -funit-at-a-time
#pragma -falign-functions
#pragma -fcrossjumping
#pragma -finline-functions
#pragma -fweb
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    } 
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n;
struct node
{
    int v,nxt;
}s[maxn];
int head[maxn],tot;
inline void add(int x,int y)
{
    s[++tot].v=y;
    s[tot].nxt=head[x];
    head[x]=tot;
}
int hson[maxn],len[maxn];//重儿子 ---- 链长 
inline void dfs1(int x)//长链剖分 
{
//    cout<<"x="<<x<<endl;
//    system("pause");
    len[x]=1;
    for(rg int i=head[x];i;i=s[i].nxt)
    {
        int v=s[i].v;
        dfs1(v);
        if(len[v]+1>len[x])
        {
            len[x]=len[v]+1;
            hson[x]=v;
        }
    }
}
int top[maxn];//每个节点所在链的最顶端的节点
inline void dfs2(int x,int topf)//x--当前节点 topf--当前节点所在链的最顶端的节点 
{
    top[x]=topf;
    if(hson[x]==0) return ;//没有儿子的话就返回
    dfs2(hson[x],topf);//这里优先处理重儿子 因为重儿子编号要连续
    for(rg int i=head[x];i;i=s[i].nxt)
    {
        int v=s[i].v;
        if(v==hson[x]) continue;//因为处理过重儿子了所以不需要再次dfs下去
        dfs2(v,v);//每个轻儿子都有一条以自己开始的链 
    } 
}
inline void pre_work()
{
    tot=0;
    for(rg int i=0;i<=n+5;++i) 
    {
        top[i]=0;
        hson[i]=0;
        len[i]=0;
        head[i]=0;
        s[i].v=s[i].nxt=0;
    }
}
inline void solve()
{
    
    n=read();
    pre_work();
    for(rg int i=2;i<=n;++i)
    {
        int x=read();
        add(x,i);
    }
    dfs1(1);
    dfs2(1,1);
    vector<int>ans;
    for(rg int i=1;i<=n;++i)
    {
        if(i==top[i]) ans.push_back(len[i]);
    }
    sort(ans.begin(),ans.end(),greater<int>());
    int temp=ans.size(),cnt=0;
    for(rg int i=0;i<ans.size();++i)
    {
        temp=min(temp,ans[i]+cnt);
        cnt++;
    }
    cout<<temp<<endl;
} 
int t;
signed main()
{
    t=read();
    while(t--)
    {
        solve();
    }
    return 0;
}
View Code

 

标签：Contest,int,Regional,Xian,long,while,pragma,inline,define
From： https://www.cnblogs.com/sakuya726/p/17660692.html

相关文章

  • The 2022 ICPC Asia Nanjing Regional Contest (G. Inscryption)
    Problem-G-Codeforces反悔贪心#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#defineendl"\n"constintN=1e6+5;inlineintgcd(inta,intb){returnb>0?gcd(b,a%b):a;}intmain(){ios::......
  • The 2022 ICPC Asia Nanjing Regional Contest（A.Stop, Yesterday Please No More）
    模拟边界（不是袋鼠）移动，通过二维差分维护左上角和右下角，同时注意排除重复的点#include<bits/stdc++.h>usingnamespacestd;#defineendl"\n"typedeflonglongll;constintN=1e3+5;intf[N][N];intmain(){ios::sync_with_stdio(false),cin.tie(0),cout.......
  • AtCoder Beginner Contest 215
    [ABC215F]DistMax2 二分出min(|xi-xj|,|yi-yj|)，双指针维护是否存在满足条件的点对（i，j），假如二分当前值是x，那么|xi-xj|>=x&&|yi-yj|>=x #include<bits/stdc++.h>usingnamespacestd;#defineendl"\n"typedeflonglongll;consti......
  • 暑假集训D24 2023.8.22 contest I
    C.CityFolding题意:有一个由\(2^n\)条等长线段组成的线,你可以进行\(n\)次对折,可以从左向右对折或从右向左对折,给出初始时线段的编号\(P\),问如何对折\(n\)次才能使对折后该线段恰好在从下往上数第\(H\)层?\(\operatorname{Solution}\)构造可以倒过来考虑这个......
  • 暑假集训D23 2023.8.21 contestH
    H.HardcoreHangman题意:现在有一个隐藏字符串,你可以进行最多\(7\)次询问,每次询问一个字符串,系统会回答这个字符串中所有字符的位置(从小到大依次).现在请你做出合理的询问,找出这个隐藏的字符串.\(\operatorname{Solution}\)......
  • AtCoder Beginner Contest 314
    A-3.14#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongint32_tmain(){ios::sync_with_stdio(0),cin.tie(0);strings="141592653589793238462643383279502884197169399375105820974944592307816406286208998628034......
  • AtCoder Beginner Contest 315
    A-tcdr#include<bits/stdc++.h>usingnamespacestd;int32_tmain(){strings;cin>>s;for(autoi:s){if(i!='a'andi!='e'andi!='i'andi!='o'andi!='u�......
  • AtCoder Beginner Contest 287 - C (图论简单题)
    目录C-PathGraph?C-PathGraph?题意判断给定的无向简单图是不是一条链思路n个顶点m条边的无向图若为一条链，那么边数\(m=n-1\)，n个顶点相互可达，任意一个顶点的度不超过2利用并查集判整体连通性，在建图时统计度数，最后判断即可由此，n个顶点，n-1条边的无向连通......
  • The 2023 ICPC China Shaanxi Provincial Programming Contest
    链接：https://qoj.ac/contest/1290A表达式板子。\(O(|s|)\)。#include"bits/stdc++.h"usingnamespacestd;usingi64=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);strings;cin>>s;intn=s......
  • AtCoder Beginner Contest 315 - E (toposort)
    目录E-PrerequisitesE-Prerequisites题意n本书，序号1~n。给定阅读每本书之前必须要看的书的序号。请你输出任意一种看第一本书所需看书数量最少的方法思路利用拓扑序列先对书之间的制约关系建图，再利用bfs找到包含书本1的连通块，再对全图进行拓扑排序得到拓扑序列......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99