Codeforces Round #586 (Div. 1 + Div. 2)

A. Cards

给出一个字符串,然后你要改变字母的顺序,然后把它拼成最大的英文二进制,然后输出这个二进制…

分析:

直接暴力先搞1,再搞2就好了…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n;
string s;
int zz[300];
signed main()
{
    read(n);
    cin>>s;
    for(int i=0;i<n;i++)    
        zz[s[i]]++;
    while(zz['o']&&zz['n']&&zz['e'])
        printf("1 "),zz['o']--,zz['n']--,zz['e']--;
    while(zz['o']&&zz['z']&&zz['e']&&zz['r'])
        printf("0 "),zz['o']--,zz['z']--,zz['e']--,zz['r']--;
    puts("");
    return 0;
}

B. Multiplication Table

题面:

给出一个矩阵,然后有一个数列,满足M_{ij}=a_i\times a_j,然后给出矩阵的对角线是0,然后让你输出原来的a数列…

分析:

我们直接用M_{ij}\times M_{jk}/M_{ik}就可以求出a_i ^2,然后我们就可以顺势求出2\to n-1之间的所有a_i,然后剩余两个手到擒来…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL n,ans[1010];
LL Map[1010][1010];
signed main()
{
    read(n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            read(Map[i][j]);
    for(int i=2;i<n;i++)
        ans[i]=sqrt(Map[i-1][i]*Map[i][i+1]/Map[i-1][i+1]);
    ans[1]=Map[1][2]/ans[2];
    ans[n]=Map[n-1][n]/ans[n-1];
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    puts("");
    return 0;
}

C. Substring Game in the Lesson

题面:

给出一个字符串,然后刚开始有l=r=k,两人轮流进行操作.
操作就是选一个l’\le l \ r\le r’,要求选出的串的字典序严格小于原来的串,然后不能操作的人输…
然后你要输出k=1\to len的所有解..

分析:

我们发现,一开始串长是1,那么我们必须再前面找一个字母小于当前字母的才行,然后我们发现如果找不到,就是MIKE赢,否则我们就选左边最小的那个,然后我们直接取到底,下一个人必然没得取…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int len;
string s;
int num[1000];
signed main()
{
    cin>>s;
    len=s.length();
    for(int i=0;i<len;i++)
    {
        int flag=0;
        for(int j=0;j<s[i]-'a';j++)
            if(num[j])
                flag=1;
        if(flag) puts("Ann");
        else puts("Mike");
        num[s[i]-'a']++;
    }
    return 0;
}

D. Alex and Julian

题面:

我们现在有一些数字a_i,然后我们构造一个图,满足|x-y|=a_ix,y之间有边相连,然后我们要使这个图最终可以构造称一个二分图,我们需要删掉一些数字…
我们考虑那些数字可以共存..

a_i\times x=a_j\times y\\
x\equiv y (mod 2)

也就是说a_i,a_j的约分以后要都是奇数才可以共存…
然后我们就只要把所有a_i分成2^x \times k_i,k_i \mod 2=0的形式,只有那些x相同的才可以共存,那么我们直接从里面选一个最大的集合,然后把其他都删掉就好了…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=2e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL n,x[N];
LL num[100],ans,zz;
signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(x[i]);
    for(int i=1;i<=n;i++) 
    {
        LL flag=0,t=x[i];
        while(t%2==0)
            flag++,t/=2;
        num[flag]++;
    }
    for(int i=0;i<=100;i++)
        if(num[i]>ans)
        {
            ans=num[i];
            zz=i;
        }
    ans=n-ans;
    printf("%lld\n",ans);
    for(int i=1;i<=n;i++)
    {
        LL flag=0,t=x[i];
        while(t%2==0)
            flag++,t/=2;
        if(flag!=zz) 
            printf("%lld ",x[i]);
    }
    puts("");
    return 0;
}

E. Tourism

题面:

给你一个无向图,和n个点值,然后给你一个起点,要求你不可以连续走同一条边,然后让你输出可以得到的最大权值(每个点只能算一次)…

分析:

这个题目我已开始想到的是tarjan缩点,然后被\times掉了,接下来去问了Vanyueyang大佬,才知道怎么写..
我们发现先找一棵生成数,如果一个点子树里有环,那么这个环和到根的路径都可以有去有回,也就是随便走,其他的点就是由去无回的然后我们就是求最后生成树上的最大值和了…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=2e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL ans,anss,cost[N];
int n,m,s,val[N],fa[N],vis[N],tag[N];
struct Edge{int next,to;} edge[N<<2];
int head[N],cnt;
void add(int u,int v){edge[++cnt]={head[u],v}; head[u]=cnt;}
void insert(int u,int v){add(u,v); add(v,u);}
void dfs(int now)
{
    vis[now]=1;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa[now]) continue;
        if(vis[to])
        {
            int flag=now;
            while(!tag[flag])
                ans+=val[flag],tag[flag]=1,flag=fa[flag];
            continue;
        }
        fa[to]=now;
        dfs(to);
    }
}
void dfs_ans(int now)
{
    if(!tag[now]) 
    {
        cost[now]=cost[fa[now]]+val[now];
        anss=max(anss,cost[now]);
    }
    if(vis[now]>=2) return;
    vis[now]++;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa[now]) continue;
        dfs_ans(to);
    }
}
signed main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) read(val[i]);
    for(int i=1,u,v;i<=m;i++) read(u),read(v),insert(u,v);
    read(s); vis[s]=1; fa[s]=s;
    ans=val[s];tag[s]=1;
    dfs(s);
    dfs_ans(s);
    printf("%lld\n",ans+anss);
    return 0;
}

F. Gardener Alex

题意:

给你一个数列,然后你可以一个一个吧数从开头拿到结尾,然后问这过程中整个数列构成的笛卡尔树的最小深度是多少..

分析:

我们可以把整个串重复一遍然后建一棵笛卡尔树,然后每次我们只有树上的一些点有用,要求的就是这些点到根的长度…因为那些没有用的点不会改变当前需要的笛卡尔树的深度,所以我们可以直接树上打标记算..

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=2e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
#define lson(_) node[_].ch[0]
#define rson(_) node[_].ch[1]
int n,x[N<<1],root,dfns,ans,anss;
struct Node{int ch[2],val,dfn,max_dfn;} node[N<<1]; 
stack<int> st;
int tree[N<<3],tag[N<<3];
void push_down(int now)
{
    tree[now<<1]+=tag[now];
    tree[now<<1|1]+=tag[now];
    tag[now<<1]+=tag[now];
    tag[now<<1|1]+=tag[now];
    tag[now]=0;
}
void change(int now,int l,int r,int ql,int qr,int k)
{
    if(ql<=l&&r<=qr)
    {
        tree[now]+=k;
        tag[now]+=k;
        return;
    }
    if(qr<l||r<ql) return;
    int mid=(l+r)>>1;
    push_down(now);
    change(now<<1,l,mid,ql,qr,k);
    change(now<<1|1,mid+1,r,ql,qr,k);
    tree[now]=max(tree[now<<1],tree[now<<1|1]);
}
void dfs(int now,int dep)
{
    if(!now) return;
    node[now].dfn=++dfns;
    dep+=node[now].val;
    change(1,1,n*2,node[now].dfn,node[now].dfn,dep);
    dfs(lson(now),dep);
    dfs(rson(now),dep);
    node[now].max_dfn=dfns;
}
signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(x[i]),x[i+n]=x[i];
    for(int i=1;i<=n*2;i++)
    {
        if(x[i]==1&&!root) root=i;
        int flag=0;
        while(!st.empty()&&x[st.top()]>x[i])
            flag=st.top(),st.pop();
        lson(i)=flag;
        if(!st.empty())
            rson(st.top())=i;
        st.push(i);
    }
    for(int i=1;i<=n;i++) node[i].val=1;
    dfs(root,0);
    ans=tree[1];
    for(int i=1;i<n;i++)
    {
        change(1,1,n*2,node[i].dfn,node[i].max_dfn,-1);
        change(1,1,n*2,node[i+n].dfn,node[i+n].max_dfn,1);
        if(ans>tree[1])
            ans=tree[1],anss=i;
    }
    printf("%d %d\n",ans,anss);
    return 0;
}

关于“Codeforces Round #586 (Div. 1 + Div. 2)”我的2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注