ICPC2022昆明站补题
Primo Pan
  2022-04-22 13:54:23 2022-04-22 13:54    

K. King of Gamers

题目大意

给了你一个的比例，从第1次开始，之前 胜利或失败都统计进去，有一个获胜比。如果当前的 比例比给出的比例大，那么就会这一次就会输，反之就赢，问n次比赛最后的胜利次数。

Solution

签到题，打表可知。数学推理的话，假设最后的答案是x，可以知道分母是n。 有，移一下项 有，把x代进n-1，去判断一下最后一次🉑️不🉑️。 省去检验的话可以发现最后答案是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int T;

ll n,a,b;

int main()
{
    cin>>T;
    while (T--)
    {
        cin>>n>>a>>b;
        ll ans=(n-1)*a/b+1;
        cout<<ans<<endl;
    }
}

D. Divisions

题目大意

构造一个序列，这个序列可以被分为一个非升和一个非降的自序列。 现在要求你构造的这个序列一共有k种不同的分法。

Solution

0或1的时候糊两个数据特判一下。

剩下的数据，考虑构造。如果整个序列是空的，那么显然答案只有一种分法,{}{}。我们现在加入第一个数进来，假如是1，可以放在左右任意一个集合中，答案是2。 在刚才的2个集合的基础上，可以放进任意一个集合里，又把答案*2。所以这样可以凑出所有种。考虑非的情况，如果我们加一个比之前所有数都要大的数。可以知道 如果要把新的那个数塞进非降序列，必须把非降序列清空，所以答案会比刚才多1。 这个时候如果再加一个2进来，答案会+2，然后是+4。如果再加一个比2大的数进来，那么又反复从1开始计算。如此一来就可以把所有的清空都覆盖进去了。 

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int T;

ll n,a,b;

int main()
{
   cin>>n;
   if (n==0)
   {
       puts("4");
       puts("8 9 4 6");
       return 0;
   }
   if (n==1)
   {
       puts("6");
       puts("1 1 4 5 1 4");
       return 0;
   }
   ll st=1,cur=0,ans=1;
   vector<int> G;
   while (ans<n)
   {
       if (ans+(1ll<<cur)<=n)
       {
           ans+=(1<<cur);
           cur++;
           G.push_back(st);
       }
       else{
           st++;
           cur=0;
       }
   }
   int L=G.size();
   cout<<L<<endl;
   for (int i=0;i<L;i++)
       cout<<G[i]<<" ";
   return 0;
}

F.Find the Maximum

题目大意

给你一棵点带权的树。让你找出一条路径。路径上所有点权的平均值是ave，现在要你求整个树的最大的

Solution

套了层皮，那个二次函数的x就直接找顶点就行了。实际上就是找树上平均值（的绝对值）最大的一条路径。然后可以二分，但这题可以给出一个引理，就是树上路径平均值最大的话结点一定不会超过3个。 比如说现在有了9，8，9。那么再加一个如果是9，那么直接9,9就最大了，如果比9来得小，那么还不如9，8，9来得优。同理再序列里找连续的平均值最大的一串数也是这个道理。 

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
#include <bits/stdc++.h>
#define ll long long
#define maxn 1000010
#define ld long double
using namespace std;


int n;
int w[maxn];
vector<int> val[maxn];

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>w[i];
    for (int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        val[x].push_back(w[y]);
        val[y].push_back(w[x]);
    }
    for (int i=1;i<=n;i++)
        sort(val[i].begin(),val[i].end());
    ld ans=-1e100;
    for (int i=1;i<=n;i++)
    {
        int N=val[i].size();
        ld cur=(1.0*w[i]+val[i][N-1])/2;
        ans=max(ans,cur);
        cur=(1.0*w[i]+val[i][0])/2;
        ans=max(ans,-cur);
        if (val[i].size()>=2) {
            cur = (1.0 * w[i] + val[i][N - 1] + val[i][N - 2]) / 3;
            ans = max(ans, cur);
            cur=(1.0*w[i]+val[i][0]+val[i][1])/3;
            ans=max(ans,-cur);
        }
    }
    ans=ans*ans/4;
    cout<<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}

B.Blocks

题目大意

平面上给你n个矩阵，坐标都为正整数，给你左下角端点和右上角端点。然后给你另一个矩阵W*H（题目感觉有漏洞，没有说这个W*H就是最大的。 每次等概率地选择n个矩阵中的一个把它涂黑，问最后把W*H涂黑的期望次数是多少。n非常小，小于或等于10。

Solutions

n这么小，一眼状压。把坐标离散化一下，会发现总共也没多少个点，对于每一个压缩的状态，直接暴力涂点判断即可。

经典的期望dp模型，涂格子，现在有n个格子，每次随机涂一个，问涂满m个格子的期望数。 经典逆推。f[i]表示已经涂了i个格子，到涂满m个还要多少步。

有，，转化一下 ，这一题f[i+1]是把当前状态异或上1后的状态相加，就是(n-i)个f[S^k]，所以把它们累加后，加上n，除以(n-i)就得到了f[i]。注意离散化和暴力涂格子别写炸，离散化后给的是格点，涂的是格子，记得循环到n-1（一开始写炸了） 

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
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
#define ll long long
#define maxn 50
const int mod=998244353;

using namespace std;

ll qpow(ll x,ll n)
{
    ll ans=1;
    while (n)
    {
        if (n&1)
            ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;
        n>>=1;
    }
    return ans;
}

struct Rect{
    int x1,y1,x2,y2;
}rec[maxn];
int n,W,H;
int w[50],h[50],w1=0,h1=0;
int state[(1<<10)+1],cnt[(1<<10)+1];
int vis[50][50];
ll dp[(1<<10)+1];
int check()
{
    for (int x=1;x<W;x++)
        for (int y=1;y<H;y++)
            if (vis[x][y]==0)
            {
                return 0;
            }
    return 1;
}
int main()
{
   // cin>>n;
   int T;
   cin>>T;
   while (T--)
   {
       w1=0;
       memset(cnt,0,sizeof(cnt));
       memset(dp,0,sizeof(dp));
       h1=0;
       cin>>n;
       cin>>W>>H;
       w[++w1]=W;
       h[++h1]=H;
       for (int i=1;i<=n;i++)
       {
           cin>>rec[i].x1>>rec[i].y1;
           w[++w1]=(rec[i].x1);
           h[++h1]=rec[i].y1;
           cin>>rec[i].x2>>rec[i].y2;
           w[++w1]=(rec[i].x2);
           h[++h1]=rec[i].y2;
       }
       sort(w+1,w+1+w1);
       sort(h+1 ,h+1+h1);
       w1=unique(w+1,w+1+w1)-w-1;
       h1=unique(h+1,h+1+h1)-h-1;
       W=lower_bound(w+1,w+1+w1,W)-w;
       H=lower_bound(h+1,h+1+h1,H)-h;
       for (int i=1;i<=n;i++)
       {
           rec[i].x1=lower_bound(w+1,w+1+w1,rec[i].x1)-w;
           rec[i].x2=lower_bound(w+1,w+1+w1,rec[i].x2)-w;
           rec[i].y1=lower_bound(h+1,h+1+h1,rec[i].y1)-h;
           rec[i].y2=lower_bound(h+1,h+1+h1,rec[i].y2)-h;
       }
       int S=(1<<n)-1;

       for (int s=S;s>=0;s--)
       {
           state[s]=1;
           memset(vis,0,sizeof(vis));
           for (int k=1;k<=n;k++)
           {
               if (s&(1<<(k-1)))
               {
                   cnt[s]++;
                   for (int x=rec[k].x1;x<rec[k].x2;x++)
                       for (int y=rec[k].y1;y<rec[k].y2;y++)
                           vis[x][y]=1;
               }
           }
           state[s]=check();

       }
       if (!state[S])
       {
           puts("-1");
           continue;
       }
       for (int s=S;s>=0;s--)
       {
           if (state[s]==1)
           {
               dp[s]=0;
               continue;
           }
           ll sum=0;
           for (int k=1;k<=n;k++)
           {
               if (!(s&(1<<(k-1))))
               {
                   sum=(sum+dp[s|(1<<(k-1))])%mod;
               }
               ll inv=qpow(n-cnt[s],mod-2);
               dp[s]=(ll)(sum+n)*inv%mod;
               dp[s]%=mod;
           }
       }
       cout<<dp[0]<<endl;
   }
}

E.Easy String Problem

题目大意

给你一个字典集大小为n的长度为n的字符串。现在对于每一个询问L，R，问你把包含[L,R]的子串删掉后能得到多少本质不同的字符串数量。

Solutions

首先删除后本质相同的字符串，删掉的字符串长度也是相同的。考虑本质相同的字符串的情况，如果[l,r]（有l<=L<=R<=r)，有l-1=r，那么[l-1,r-1]和[l,r]本质就是相同的，其实不难理解。 那么对于每一个[L,R]的询问，所有的可行方案数量是L*(n-R+1)，那么我们只要把重复的剪掉就行，重复的数量就是[1,L]和[R,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
//
// Created by Administrator on 2022/4/22.
//
#include <bits/stdc++.h>
#define maxn 100010
#define ll long long
using namespace std;
int sq,n,q;
int a[maxn];
ll ans[maxn],res;
int cl[maxn],cr[maxn];
int L,R;
struct Seg{
    int id,l,r;
    bool operator < (const Seg & b) const{
        if (l/sq!=b.l/sq)
            return l<b.l;
        if (l/sq&1)
            return r<b.r;
        return r>b.r;
    }
}req[maxn];

int main()
{
    cin>>n;
    sq=sqrt(n);
    for (int i=1;i<=n;i++)
        cin>>a[i];
    cin>>q;
    for (int i=1;i<=q;i++)
    {
        req[i].id=i;
        cin>>req[i].l>>req[i].r;
    }
    sort(req+1,req+1+q);
    L=1,R=n;
    res=0;
    for (int i=1;i<=q;i++)
    {
        while (L<req[i].l)
        {
            res+=cr[a[L]];
            cl[a[L]]++;
            L++;
        }
        while (L>req[i].l)
        {
            L--;
            cl[a[L]]--;
            res-=cr[a[L]];
        }
        while (R<req[i].r)
        {
            R++;
            cr[a[R]]--;
            res-=cl[a[R]];
        }
        while (R>req[i].r)
        {
            res+=cl[a[R]];
            cr[a[R]]++;
            R--;
        }
        ans[req[i].id]=1ll*L*(ll)(n-R+1)-res;
    }
    for (int i=1;i<=q;i++)
        cout<<ans[i]<<endl;
    return 0;
}