Atcoder Regular Contest 111

Atcoder Regular Contest 111

ACM、Codeforces&Atcoderadmin发表留言

好久不见甚是想念！时隔近三年再打atcoder，还是熟悉的味道，还是熟悉的毒瘤思博题。

B – Reversible Cards

题意

给n对卡片，每一对卡片上都有颜色，每次可以从一对中挑选出一张卡片。求最多可以挑选出多少种颜色

做法

将两张卡片的颜色连边，考虑每个大小为v连通块，若该连通块是一棵树，则对答案贡献是v-1。若该连通块不是一棵树，则对答案的贡献是v。dfs统计即可

源代码
#include<bits/stdc++.h>
#define maxn 400010
using namespace std;
int n;
struct node{
    int to;
    node*next;
}*con[maxn];
void addedge(int x,int y){
    node*p=new node;
    p->to=y;
    p->next=con[x];
    con[x]=p;
}
int cnt;
bool vis[maxn],tag;
void dfs(int v,int fa){
    vis[v]=true;cnt++;
    for(node*p=con[v];p;p=p->next)
        if(p->to!=fa){
            if(vis[p->to]) tag=true;
            else dfs(p->to,v);
        }
}
int x,y,ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&x,&y),addedge(x,y),addedge(y,x);
    for(int i=1;i<=400000;++i)
        if(!vis[i]) {tag=false;cnt=0;dfs(i,0);if(tag) ans+=cnt;else ans+=cnt-1;}
    cout<<ans;
    return 0;
}

D – Orientation

题意

给一张n个点m条边的无向图，以及c_i数组。对于每条边，使其变为有向边。最终满足第i个点可以到达c_i个点，输出所有有向边的方案

做法

很容易有以下结论：
1. 两个相邻的点处在同一个强连通分量中等价于他们可到达的点数相同。
2. 若两个相邻的点i,j满足c_i<c_j，那么该边的方向必然是从j\rightarrow i
所以我们可以先把边两端c不同的边拿出来确定方向。然后再dfs一遍，先把环的方向给跑出来，其余的强连通分量内部的边随意确定。注意，这里的dfs不是传统意义上遍历每一个点的dfs，而是遍历每一条边，并通过dfs的顺序确定边的方向

源代码
#include<bits/stdc++.h>
#define maxn 5010
using namespace std;
struct node{
    int to;
    node*next;
}*con[maxn];
void addedge(int x,int y){
    node*p=new node;
    p->to=y;
    p->next=con[x];
    con[x]=p;
}
int n,m;
int x,y,a[maxn],b[maxn],c[maxn];
bool mp[maxn][maxn];
void dfs(int v,int fa){
    for(node*p=con[v];p;p=p->next)
    if(p->to!=fa) {
        if(mp[v][p->to]||mp[p->to][v]) continue;
        mp[v][p->to]=true;
        dfs(p->to,v);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d%d",&a[i],&b[i]),addedge(a[i],b[i]),addedge(b[i],a[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&c[i]);
    for(int i=1;i<=m;++i)
        if(c[a[i]]>c[b[i]]) mp[a[i]][b[i]]=true;
        else if(c[b[i]]>c[a[i]]) mp[b[i]][a[i]]=true;
    for(int i=1;i<=n;++i)
        dfs(i,0);
    for(int i=1;i<=m;++i)
        if(mp[a[i]][b[i]]) puts("->");
        else puts("<-");
    return 0;
}

C – Too Heavy

题意

很复杂emm 大概是有n个人n个包，每个人每个包都有重量，记为a_i,b_i一开始第i个人拥有的是第p_i个背包。要求通过尽可能少的次数交换两人的背包，使得第i个人拥有第i个背包，同时还需要满足交换的过程中背包的重量要严格小于人的重量，否则就不能参与交换，输出交换得到方案。

做法

很容易有结论：方案不存在时，当且仅当某个人初始的时候拥有的背包就已经超重而且不是自己的背包（这样就无法进行交换了
之后考虑将第i个人以及其拥有的背包p_i连边。由于p_i是n的一个全排列，所以这个图由若干个环构成（有那么点点像置换群的意思哈哈）先不考虑交换时需要满足的重量限制，发现要将一个大小为v的环中所有的点都拥有自己的背包，需要进行v-1次操作，这是答案的一个下界。现我们来证明这个答案下界在需要满足重量限制时依然可以构造出方案。我们考虑一个环中人重量最小的元素，我们贪心地将其满足条件，由于交换之后重量小的元素已经满足自己拿了自己地背包，故不需要考虑需不需要继续交换，即不需要考虑与其交换的人的背包重量。而显然重量最小的元素在交换前是不疲惫的，否则将不存在解决方案。所以将他的背包给重量更大的人时是可以满足继续交换的条件的。每进行一次这样的操作，大环就会被拆分成一个自环和一个size为v-1的小环。

坑点

每次dfs找环的时候没有把记录环大小的变量清零，从而导致TLE

#include<bits/stdc++.h>
#define maxn 200050
using namespace std;
int n,a[maxn],b[maxn],p[maxn],np[maxn];
bool vis[maxn];
int sz,anss;
struct nod{
    int pos,wei;
}dl[maxn];
struct node{
    int x,y;
}ans[maxn];
bool cmp(nod aa,nod bb){
    return aa.wei<bb.wei;
}
inline int read()
{
    int x=0;char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x;
}
void dfs(int v){
    if(vis[v]){
        sort(dl+1,dl+sz+1,cmp);
        for(int i=1;i<=sz;++i){
            int x=dl[i].pos,y;
            y=np[dl[i].pos];
            if(x==y) continue;
            swap(p[x],p[y]);
            np[p[x]]=x;
            np[p[y]]=y;
            anss++;
            ans[anss].x=x;ans[anss].y=y;
        }
        return;
    }
    vis[v]=true;
    dl[++sz].pos=v;
    dl[sz].wei=a[v];
    dfs(p[v]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        a[i]=read();
    for(int i=1;i<=n;++i)
        b[i]=read();
    for(int i=1;i<=n;++i)
        p[i]=read(),np[p[i]]=i;
    for(int i=1;i<=n;++i)
        if(a[i]<=b[p[i]]&&i!=p[i]){
            cout<<-1;
            return 0;
        }
    for(int i=1;i<=n;++i)
        if(!vis[i]){
            sz=0;
            dfs(i);
        }
    cout<<anss<<endl;
    for(int i=1;i<=anss;++i)
        printf("%d %d\n",ans[i].x,ans[i].y);
    return 0;
}

A – Simple Math 2

题意&做法

求\lfloor \frac{10^N}{M}\rfloor mod M
考虑带余除法10^N=r+pM^2
\Rightarrow \frac{10^N}{M}=\frac{r}{M}+pM
\Rightarrow \lfloor \frac{10^N}{M}\rfloor=\lfloor \frac{r}{M} \rfloor+pM
\Rightarrow ans=\lfloor\frac{r}{M}\rfloor
其中r为10^N模M方的余数

源代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll m,n;
ll ksm(ll a,int v){
    ll res=1;
    for(;v;v>>=1,(a*=a)%=(m*m))
        if(v&1) (res*=a)%=(m*m);
    return res;
}
int main(){
    cin>>n>>m;
    cout<<(ksm(10,n)/m)<<endl;
    return 0;
}

留下回复