Codeforces Round #686 (Div. 3)补题

发表于 更新于 分类于 阅读次数：

这场题目真的很简单，感觉如果能回复手速的话，以后类似的div3能做到AK？

A. Special Permutation

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<n;
        for(int i=1;i<n;i++)
            cout<<' '<<i;
        cout<<endl;
    }
    return 0;
}

B. Unique Bid Auction

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
int a[maxn];
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int ans=inf;
        vector<pii>rec;
        map<int,int>mp;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            mp[a[i]]++;
            rec.push_back(pii(a[i],i));
        }
        sort(rec.begin(),rec.end());
        for(auto &i:rec)
        {
            if(mp[i.ff]==1)
            {
                ans=i.ss;
                break;
            }
        }
        if(ans==inf)
            cout<<-1<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}

C. Sequence Transformation

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
int a[maxn],dp[maxn],pre[maxn],last[maxn];
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            last[i]=inf;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            dp[i]=pre[i]=inf;
            last[a[i]]=i;
        }
        int ans=inf;
        for(int i=1;i<=n;i++)
        {
            if(pre[a[i]]==inf)
            {
                pre[a[i]]=i;
                dp[a[i]]=(i==1?0:1);
            }
            else{
                if(pre[a[i]]<i-1)
                    dp[a[i]]++;
                pre[a[i]]=i;
            }
            if(i==last[a[i]]&&i<n)
                dp[a[i]]++;
        }
        for(int i=1;i<=n;i++)
            ans=min(ans,dp[i]);
        cout<<ans<<endl;
    }
    return 0;
}

D. Number into Sequence

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int>pii;
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
ll qmod(ll a,ll b)  //快速幂
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ll t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        vector<pii>f;
        ll now=n,ans=0,val=0;
        for(ll i=2;i*i<=now;i++)
            if(now%i==0)
            {
                int cnt=0;
                while(now%i==0)
                {
                    now/=i;
                    cnt++;
                }
                f.push_back(pii(i,cnt));
                if(cnt>ans)
                {
                    ans=cnt;
                    val=i;
                }
            }
        if(now>1)
        {
            f.push_back(pii(now,1));
            if(1>ans)
            {
                ans=1;
                val=now;
            }
        }
        cout<<ans<<endl;
        ll other=val;
        for(auto &i:f)
        {
            if(i.ff!=val)
                other*=qmod(i.ff,i.ss);
        }
        for(int i=1;i<ans;i++)
            cout<<val<<' ';
        cout<<other<<endl;
    }
    return 0;
}

E. Number of Simple Paths

题意

求基环树上简单路径数。

思路

先求出环上到环上的简单路径数，然后统计以环上每个节点为根的子树的大小，每新加入一棵子树，再统计一边贡献。

  • 环上路径数 $= n\times(n-1)$
  • 一棵树内简单路径数 $= \frac{n\times (n-1)}{2}$

坑点①，子树到树根只有一种路径。

坑点②，环上一个节点可能有多个子树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define int ll
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
vector<int>G[maxn];
int loop[maxn],vis[maxn],fa[maxn],tim=0,cnt=0;
int stk[maxn],ind=0;
bool c[maxn],flag=0;
void getloop(int x)
{
    if(flag)
        return;
    vis[x]=++tim;
    stk[++ind]=x;
    for(int &v:G[x])
    {
        if(v==fa[x])
            continue;
        if(flag)
            return;
        if(vis[v])
        {
            c[v]=1;
            cnt=1;
            for(int i=ind;stk[i]!=v;i--)
            {
                c[stk[i]]=1;
                cnt++;
            }
            flag=1;
            return;
        }
        else{
            fa[v]=x;
            getloop(v);
        }
    }
    ind--;
}
ll dfs(int x,int fa)
{
    int now=1;
    vis[x]=1;
    for(int &v:G[x])
    {
        if(v==fa||c[v]||vis[v])
            continue;
        now+=dfs(v,x);
    }
    return now;
}
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,n,u,v;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            G[i].clear();
            loop[i]=vis[i]=0;
            fa[i]=0;
            c[i]=0;
        }
        tim=cnt=0;
        ind=0;
        flag=0;
        for(int i=1;i<=n;i++)
        {
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        getloop(1);
        ll ans=cnt*(cnt-1);
        for(int i=1;i<=n;i++)
            vis[i]=0;
        for(int i=1;i<=n;i++)
        {
            if(c[i])
            {
                ll tmp=0,tot=0;
                for(int &v:G[i])
                {
                    if(!vis[v]&&!c[v])
                    {
                        tmp=dfs(v,v);
                        ans+=tmp*(tmp-1)/2;
                        ans+=tot*tmp;
                        tot+=tmp;
                    }
                }
                ans+=cnt*2*tot-tot;
                cnt+=tot;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
 *基环树上有多少简单路径
 *先考虑环上路径数 = n*(n-1)
 *一棵树内简单路径数 = n*(n-1)/2
 */

F. Array Partition

题意

将一个数组$a$分成三部分$[1,x],[x+1,y],[y+1,n]$，使得$max(1,x)=min(x+1,y)=max(y+1,n)$，请输出这三段的长度。

思路

枚举左面的断点，并且二分右面的断点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
//const int maxn=100005;
int a[maxn],d[maxn][20],d2[maxn][20],lg[maxn];
void init(int n)
{//d[i][j]表示以i为起点,2^j长度的最值
    for(int i=1;i<=n;i++)
    {
        lg[i]=lg[i-1]+((1<<(lg[i-1]+1))==i);
        d[i][0]=d2[i][0]=a[i];
    }
    for(int j=1;(1<<j)<=n;j++)//枚举长度
        for(int i=1;i+(1<<j)-1<=n;i++)//枚举起点,倍增+DP
        {
            d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
            d2[i][j]=min(d2[i][j-1],d2[i+(1<<(j-1))][j-1]);
        }
}
int rmq(int l,int r)
{
    int k=lg[r-l+1];
    return max(d[l][k],d[r-(1<<k)+1][k]);
}
int rmq2(int l,int r)
{
    int k=lg[r-l+1];
    return min(d2[l][k],d2[r-(1<<k)+1][k]);
}
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        init(n);
        bool ok=0;
        int x,y;//max[1,x]=min[x+1,y]=max[y+1,n]
        for(int i=1;i<=n;i++)
        {
            x=i,y=0;
            int l=i+1,r=n-1;
            int now=rmq(1,i);
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(rmq2(i+1,mid)>now||rmq(mid+1,n)>now)
                {
                    l=mid+1;
                }
                else if(rmq2(i+1,mid)<now||rmq(mid+1,n)<now)
                {
                    r=mid-1;
                }
                if(rmq2(i+1,mid)==now&&rmq(mid+1,n)==now)
                {
                    y=mid;
                    break;
                }
            }
            if(y>x&&rmq2(x+1,y)==now&&rmq(y+1,n)==now)
            {
                ok=1;
                break;
            }
        }
        cout<<(ok?"YES":"NO")<<endl;
        if(ok)
            cout<<x<<' '<<y-x<<' '<<n-y<<endl;
    }
    return 0;
}
/*
2
8
1 2 3 4 4 3 4 2
7
2 1 4 2 4 3 2
*/