Diposting di | Edited on

传送门

A - Little Pony and Crystal Mine （签到画图

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const int inf=1e9;
typedef unsigned long long ull;


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    int mid=n/2;
    for(int i=1;i<=mid;i++){
        for(int j=1;j<=n;j++){
            if(j<=mid-i+1||j>=mid+i+1)cout<<'*';
            else cout<<'D';
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++)cout<<'D';cout<<endl;
    for(int i=mid;i;i--){
        for(int j=1;j<=n;j++){
            if(j<=mid-i+1||j>=mid+i+1)cout<<'*';
            else cout<<'D';
        }
        cout<<endl;
    }

    return 0;
}

B - Little Pony and Sort by Shift

题意

给你一个数列 你每次可以把最后一个移到第一个问你最少几次可以把这个数列变成非递减的

思路

直接找到一个最小的然后判断顺时针能否相连 如果多个最小就直接-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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const int inf=1e9;
typedef unsigned long long ull;

int a[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    int pre,flag=0,pos;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(i&&a[i]<a[i-1])flag++,pos=i;
    }
    if(!flag)puts("0");
    else if(flag==1&&a[0]>=a[n-1])cout<<n-pos<<endl;
    else cout<<-1<<endl;
    return 0;
}

A - Little Pony and Expected Maximum (概率)

题意

投M面筛，分别求出最大投出i面的可能性

思路

直接判断太复杂 转换方向，发现求出一个筛子投出小于等于i很好算就等于i/m 然后n个一样的就n方

然后最大投出i面 =投出小于等于i面-投出小于等于i-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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
double dp[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=m;i++)dp[i]=pow(i*1.0/m,n);

    double ans=0;
    for(int i=1;i<=m;i++){
        ans+=(dp[i]-dp[i-1])*i*1.0;
    }
    cout<<fixed<<setprecision(10)<<ans<<endl;

    return 0;
}

B - Little Pony and Harmony Chest (dfs+状态压缩+数论)

题意

给你一个数组a 然后给你一个数组b 让你组成构成一个数组b使得数组b任意两个数的gcd=1 并且数组b和a的对应元素绝对值最小 （数组a的值小于等于30）

思路

首先发现b的值最大到60，因为如果超过60 那么还不如直接选1来的好又没有贡献公约数又没有增加值

发现60内最多17个素数

我们就枚举整个数组b的当前素数个数种类就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const int inf=1e9;
typedef unsigned long long ull;

int prime[17]={2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,53};
int dp[105][1<<17],pre[105][1<<17],num[105][1<<17];
int sta[70];
int a[150];

void dfs(int pos,int st){
    if(pos==1){
        cout<<pre[pos][st]<<" ";
        return ;
    }
    dfs(pos-1,st^(sta[pre[pos][st]]));
    cout<<pre[pos][st]<<" ";
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=2;i<60;i++){
        for(int j=0;j<17;j++){
            if(i%prime[j]==0)sta[i]|=(1<<j);
        }
    }
    for(int i=0;i<105;i++){
        for(int j=0;j<(1<<17);j++)dp[i][j]=inf;
    }
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<(1<<17);j++){
            if(dp[i][j]==inf)continue;
            for(int k=1;k<60;k++){
                if(j&sta[k])continue;
                int now=j|sta[k];
                if(dp[i+1][now]>dp[i][j]+abs(a[i]-k)){
                    dp[i+1][now]=dp[i][j]+abs(a[i]-k);
                    pre[i+1][now]=k;
                }
            }
        }
    }
    int st;
    int mx=inf;
    for(int i=0;i<(1<<17);i++){
        if(dp[n][i]<mx){
            mx=dp[n][i];
            st=i;
        }
    }
    dfs(n,st);
    return 0;
}

C - Little Pony and Summer Sun Celebration (构造 dfs)

题意

给出有n个点m条路的图，再给出一组序列如果第i个数为零表明第i个点要被访问偶数次否则要被访问奇数次，如果存在这样的路径请输出出来，否则输出-1

思路

遍历图中每个点

找一个需要经过奇数次的点开始深搜。不用担心环，比如1-2-3-1是环，走1-2-3-2-1就行。进入一个点，先把它加进队列，经过次数为1；每次探完一条边回溯的时候，先把当前点再加入队列一次（走回来了嘛），然后看这条边连的那个点的经过次数够不够，不够的话再走它一下，再回来。（把那个点加入队列，再把这个点加入队列）。

只有起点可能次数不太对，如果不对的话就不走最后回起点的那一步了也就是删掉队尾

这样其实每条边不可能走超过4n次。最后把队列输出就好了。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const int inf=1e9;
typedef unsigned long long ull;
vector<int>G[maxn];
vector<int>ans;

int a[maxn];
bool vis[maxn];
void dfs(int now,int pre){
    a[now]^=1;
    ans.push_back(now);
    vis[now]=1;
    for(auto i:G[now]){
        if(i!=pre&&vis[i]==0){
            dfs(i,now);
            ans.push_back(now);
            a[now]^=1;
            if(a[i]){
                ans.push_back(i);a[i]^=1;
                ans.push_back(now);a[now]^=1;
            }
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int root=-1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i])root=i;
    }
    if(root==-1)puts("0"),exit(0);
    dfs(root,-1);
    if(a[root])ans.pop_back(),a[root]^=1;
    for(int i=1;i<=n;i++){
        if(a[i])puts("-1"),exit(0);
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<" ";
    return 0;
}

Diposting di | Edited on

传送门

[A - Game With Sticks (签到)

题意

给出n条垂直线m条平行线他们互相相交 形成n×m条交点

现在每次取一个交点然后把过这个交点的线段全部去除

不能选择交点的失败，问你最后谁会赢

思路

很明显 交点取的最大数量和N和m的最小值有关

并且每次取一个点都肯定会有一条水平和一条竖线被取出

所以答案就是n和m的最小值的奇偶判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    if(min(n,m)%2)cout<<"Akshat"<<endl;
    else cout<<"Malvika"<<endl;
    return 0;
}

B - Sort the Array

问你能否旋转一个区间使得整个数组严格递增

思路

直接暴力枚举需反转的区间判断是否符合

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
int a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int st=0;
    for(int i=0;i<n-1;i++){
        if(a[i]>a[i+1]){
            st=i;
            break;
        }
    }
    int ed=0;
    for(int i=n-1;i>=1;i--){
        if(a[i]<a[i-1]){
            ed=i;
            break;
        }
    }
    reverse(a+st,a+ed+1);
    bool flag=1;
    for(int i=1;i<n;i++){
        if(a[i]<a[i-1])flag=0;
    }
    if(flag)cout<<"yes"<<endl<<st+1<<" "<<ed+1;
    else cout<<"no"<<endl;
    return 0;
}

C - Predict Outcome of the Game (分类讨论)

题意

三个队伍有n场比赛，你错过了K场但是你知道第一个队伍和第二个队伍的分数差的绝对值，和第二个队伍和第三个队伍分数差的绝对值，问你能否使得三个队伍分数都一样

注意！比赛不会出现平局

思路

首先N肯定要是三的倍数 不然绝对不能平均分配

然后根据题意我们得出两个不等式，假设队伍的分数分别是a.b.c

那么

那么会得出四个方程然后都比较判断一下就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;
ll n, k, d1, d2, ave, x, ok;

bool one() {
    if(n%3==0&&(k+2*d1+d2)%3==0){
        ave=n/3;
        x=(k+2*d1+d2)/3;
        if(ave>=x&&x>=(d1+d2))
            return true;
    }
    return false;
}

bool two() {
    if((k+2*d1-d2)%3==0&&(k+2*d1-d2)>=0){
        ave=n/3;
        x =(k+2*d1-d2)/3;
        if(ave>=x&&x>=d1&&ave>=(x-d1+d2))
            return true;
    }
    return false;
}


bool three() {
    if((k-2*d1+d2)%3==0&&(k-2*d1+d2)>=0) {
        ave=n/3;
        x=(k-2*d1+d2)/3;
        if(ave>=(x+d1)&&(x+d1)>=d2)
            return true;
    }
    return false;
}


bool four() {
    if((k-2*d1-d2)%3==0&&(k-2*d1-d2)>=0){
        ave=n/3;
        x=(k-2*d1-d2)/3;
        if(ave>=(x+d1+d2))
            return true;
    }
    return false;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k>>d1>>d2;
        if(n%3){
            cout<<"no"<<endl;continue;
        }
        if(one()||two()||three()||four()){
            cout<<"yes"<<endl;continue;
        }
        else cout<<"no"<<endl;

    }
    return 0;
}

D - Count Good Substrings (水题)

题意

给你只含a,b的字符串，然后相同的字符串会合并

问你有多少个奇数 和偶数的字串是回文

思路

首先只有a和b 题目难度小了很多

然后因为相同字符串会合并

所以最后回文串的只需要头尾相同就行，然后现在就是判断长度了

发现奇数的 就只要是相同奇数和奇数 偶数和偶数匹配就行

偶数就是奇数和偶数 匹配就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;

ll a[2][2];
char s[maxn];
ll odd(){
    ll ans=0;
    ans+=1LL*(a[0][1]+a[1][1]);
    ans+=1LL*a[0][1]*(a[0][1]-1LL)/2LL;
    ans+=1LL*a[1][1]*(a[1][1]-1LL)/2LL;
    ans+=1LL*a[0][0]*(a[0][0]-1LL)/2LL;
    ans+=1LL*a[1][0]*(a[1][0]-1LL)/2LL;
    ans+=1LL*(a[0][0]+a[1][0]);
    return ans;
}
ll even(){
    ll ans=0;
    ans+=a[0][0]*a[0][1];
    ans+=a[1][0]*a[1][1];
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>s+1;
    int len=strlen(s+1);
    for(int i=1;i<=len;i++){
        int id=s[i]-'a';
        int ok=i%2;
        a[id][ok]++;
    }
    cout<<even()<<" "<<odd()<<endl;
    return 0;
}

E - Devu and Flowers (组合数 卢卡斯定理 容斥定理)

题意

给你n个盒子 每个盒子有k个花，让你从n个盒子选出s朵花，求方案数

思路

首先不考虑盒子的花的数量，那么答案是

但是这时候有的盒子的花数量超出了，所以我们就要减去超出的数量

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef unsigned long long ull;

ll n,s;
ll pow_mod(ll x, ll n, ll mod){
    ll res=1;
    while(n){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll inv(ll a,ll p){return pow_mod(a,p-2,p);}
ll cal(ll a,ll b,ll p){
    if(a<b)return 0;
    if(b>a-b)b=a-b;
    ll fz=1,fm=1;
    for(ll i=0;i<b;i++){
        fz=fz*(a-i)%p;
        fm=fm*(i+1)%p;
    }
    return fz*inv(fm,p)%p;
}

ll lucas(ll a,ll b,ll p){
    if(b==0)return 1;
    return cal(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
ll f[50];

ll solve(){
    ll ans=0;
    for(int i=0;i<(1<<n);i++){
        ll sign=1,sum=s;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                sum-=(f[j]+1);
                sign*=-1;
            }
        }
        if(sum<0)continue;
        ans+=sign*lucas(sum+n-1,n-1,mod);
        ans=(ans+mod)%mod;
    }
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>s;
    for(int i=0;i<n;i++)cin>>f[i];

    cout<<solve()<<endl;
    return 0;
}

Diposting di | Edited on

传送门

A - Jzzhu and Children （签到）

题意

模拟给N个孩子发糖一次发M个 每个孩子需要a[i]个糖 如果给的糖满足孩子的需要孩子就会走，不满足就会到队伍最后 问你最后走的孩子编号

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    queue<pair<int,int> >pq;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        pq.push({a,i});
    }
    int last=-1;
    while(!pq.empty()){
        int aa=pq.front().first;
        last=pq.front().second;
        pq.pop();
        aa-=m;
        if(aa>0)pq.push({aa,last});
    }
    cout<<last;
    return 0;
}

B - Jzzhu and Sequences ( 矩阵快速幂)

题意

a[1]=x,a[2]=y,a[i]=a[i+1]+a[i-1]

让你求a[n]

思路

可以发现a[i]=a[i-1]-a[i-2];

然后就可以矩阵快速幂了，或者可以多推几项发现这个数论是6个一循环

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>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat& A,mat &B){
    mat C(A.size(),vec(B[0].size()));
    for(int i=0;i<A.size();i++)
        for(int k=0;k<B.size();k++)
        if(A[i][k])
            for(int j=0;j<B[0].size();j++)
            C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
    return C;
}
mat Pow(mat A,ll n){
    mat B(A.size(),vec(A.size()));
    for(int i=0;i<A.size();i++)B[i][i]=1;
    for(;n;n>>=1,A=mul(A,A))
        if(n&1)B=mul(B,A);
    return B;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll x,y,n;
    cin>>x>>y>>n;
    x=(x+mod)%mod;y=(y+mod)%mod;
    if(n==1)cout<<x,exit(0);
    if(n==2)cout<<y,exit(0);
    mat a=mat(2,vec(2));
    a[0][0]=1;a[0][1]=-1;
    a[1][0]=1;a[1][1]=0;
    a=Pow(a,n-2);
    mat b=mat(2,vec(1));
    b[0][0]=y;
    b[1][0]=x;
    a=mul(a,b);
    cout<<(a[0][0]+mod)%mod<<endl;
    return 0;
}

C - Jzzhu and Chocolate (思维)

题意

给你一个矩形巧克力

你可以横切竖切,但是只能在巧克力的内边并且不能破坏巧克力的内部

让你切K刀 使得最小面积最大

思路

可以发现如果K>n+m-2是不能完全切完

然后贪心的做法就是这K刀全部切同一个方向，然后不足K到的切其他方向

为什么可以全部切同一方向呢，假设我们现在有一个4×6的巧克力 我们现在在切一竖刀 变成2×6=12的巧克力 如果我们切横刀变成4乘3=12的巧克力，那么如果我们两刀都切横

1×6=6 如果两刀交叉切 变成2乘3=6的巧克力

如果两道都竖切，变成4乘2=8的巧克力 明显答案更优

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    ll n,m,k;

    cin>>n>>m>>k;
    ll cancut=n+m-2;
    ll ans=0;
    if(k>cancut)cout<<-1,exit(0);
    else{
        if(k>=n)ans=max(ans,1LL*m/(k-n+2LL));
        if(k>=m)ans=max(ans,1LL*n/(k-m+2LL));
        if(k<n)ans=max(ans,1LL*m*(n/(k+1LL)));
        if(k<m)ans=max(ans,1LL*n*(m/(k+1LL)));
    }
    cout<<ans<<endl;
    return 0;
}

D - Jzzhu and Cities (最短路)

题意

给你一个无向图，结点1为首都

有m条铁路 每条铁路有距离 同时有K条直通首都的航线 同时也有距离

现在想要关掉最多航线，同时使得首都到其他点的最短路不变

思路

一开始以为是求个最小生成树….

后来发现直接求个最短路 然后航线也参与最短路的求解中，有其他的路线更新了这个航线的距离就可以把这个航线给去掉了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m,k;
vector<pii>G[maxn];
ll d[maxn];
int vis[maxn];
int need[maxn];

int dij(){
    fill(d,d+maxn,1e18);
    d[1]=0;
    queue<int>pq;
    vis[1]=1;
    pq.push(1);
    for(int i=1;i<=k;i++){
        int u,x;
        cin>>u>>x;
        if(d[u]>x){
            d[u]=x;need[u]=1;
            if(vis[u]==0){
                pq.push(u);
                vis[u]=1;
            }
        }
    }
    while(!pq.empty()){
        int u=pq.front();pq.pop();
        vis[u]=0;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].first,x=G[u][i].second;
            if(d[v]>=d[u]+x&&need[v])need[v]=0;
            if(d[v]>d[u]+x){
                d[v]=d[u]+x;
                if(vis[v]==0){
                    vis[v]=1;
                    pq.push(v);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        k-=need[i];
    }
    return k;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,x;
        cin>>u>>v>>x;
        G[u].push_back({v,x});
        G[v].push_back({u,x});
    }
    cout<<dij()<<endl;
    return 0;
}

E - Jzzhu and Apples (大模拟+素数)

题意

给N个苹果编号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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int vis[maxn];

int prime[maxn];
bool check[maxn];
int tot;

void init(int n){
    tot=0;
    for(int i=2;i<=n;i++){
        if(!check[i]){
            prime[++tot]=i;
        }
        for(int j=1;j<=tot;j++){
            if(i*prime[j]>n)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}

vector<int>L,R;


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    init(n);
    for(int i=2;i<=tot;i++){
        vector<int>s;
        int x=prime[i];
        for(int j=x;j<=n;j+=x)
            if(!vis[j])s.push_back(j);
        int cnt=s.size();
        if(cnt&1){
            for(int j=0;j<cnt;j++){
                if(s[j]%2==0){
                    s.erase(s.begin()+j);break;
                }
            }
        }
        cnt=s.size();
        for(int j=1;j<cnt;j+=2){
            vis[s[j-1]]=1;vis[s[j]]=1;
            L.push_back(s[j-1]);R.push_back(s[j]);
        }
    }
    vector<int>even;
    for(int i=2;i<=n;i+=2)if(!vis[i])even.push_back(i);
    int cnt=even.size();
    for(int i=1;i<cnt;i+=2)L.push_back(even[i-1]),R.push_back(even[i]);
    cout<<L.size()<<endl;
    for(int i=0;i<L.size();i++)
        cout<<L[i]<<" "<<R[i]<<endl;
    return 0;
}

Diposting di | Edited on

传送门

A.DZY Loves Chessboard (签到)

题意

给你一个N×M的地图 再空地上填上白棋或者黑棋要求同色棋子不能相邻

思路

直接搜索一下

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=5e4+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[150][150];
int n,m;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void dfs(int x,int y,bool f){
    if(f)s[x][y]='W';
    else s[x][y]='B';
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<0||xx>=n||yy<0||yy>=m||s[xx][yy]!='.'){
            continue;
        }
        dfs(xx,yy,f?false:true);
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='.'){
                dfs(i,j,0);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<s[i][j];
        }
        cout<<endl;
    }
    return 0;
}

B - DZY Loves Chemistry (联通块)

题意

有一堆化学品，他们有的两个之间有化学反应，现在按一定顺序投放到一个试管中，如果投放之前试管内部有可以与当前投放的反应那么答案×2 怎么样投放答案最大，输出最大答案

思路

很容易想到最优答案就是可以反应的联通块的大小-1次方，然后多一个联通快就少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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=5e4+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int fa[maxn];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        a=find(a),b=find(b);
        fa[a]=b;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==i)ans++;
    }
    cout<<(1LL<<(1LL*n-ans*1LL));
    return 0;
}

C - DZY Loves Physics (结论)

题意

给你一个图，定义图的密度是图的点值/两点之间的边值

让你找出一个联通封闭诱导子图 使得图的密度最大

思路

假设两个点的答案是最大的 那么答案为

u和v是两个结点的值 c是他们之间的边的值

对于大于两个点的答案为

假设B的值为这个答案

那么对于任意一条边的值

对于任意的

可以变成

那么这样会得出

与上面矛盾 证毕

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=5e4+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
double a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    double ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        ans=max(ans,double((a[v]+a[u])/w));
    }
    cout<<fixed<<setprecision(15);
    cout<<ans;
    return 0;
}

D - DZY Loves FFT (随机数乱搞理论)

题意

给出一个随机数组A,B，让你对于每个

img

求出Ci

思路

可以发现A,B是完全随机的，而且暴力复杂度爆炸，

从大到小枚举排列中的数,再不断更新答案.更新过的答案就不需要再更新了

开一个优先队列保存起来,然后就是判断这前多少大的数据可不可以被取到，对于一个数钱50大的数对于他来说都没办法被取到的概率大概是

A50取50的概率分之一

优先队列的size越大概率越小

如果是在取不到就暴力一下把

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll x,n,d;
ll a[maxn],b[maxn];
ll getNextX(){
    x=(x*37+10007)%1000000007;
    return x;
}
void initAB(){
    int i;
    for(i = 0; i < n; i = i + 1){
        a[i] = i + 1;
    }
    for(i = 0; i < n; i = i + 1){
        swap(a[i], a[getNextX() % (i + 1)]);
    }
    for(i = 0; i < n; i = i + 1){
        if (i < d)
            b[i] = 1;
        else
            b[i] = 0;
    }
    for(i = 0; i < n; i = i + 1){
        swap(b[i], b[getNextX() % (i + 1)]);
    }
}
priority_queue<pair<ll,int> >all;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>d>>x;
    initAB();
    vector<int>B;
    for(int i=0;i<n;i++)if(b[i])B.push_back(i);
    for(int i=0;i<n;i++){
        all.push({a[i],i});
        bool yes=false;
        priority_queue<pair<ll,int> >now;
        for(int j=0;j<50&&!all.empty();j++){
            ll value=all.top().first;
            int id=all.top().second;
            if(!yes&&b[i-id]){
                cout<<value<<endl;
                yes=true;
            }
            now.push(all.top());
            all.pop();
        }
        if(!yes){
            ll ans=0;
            for(int j=0;j<B.size()&&B[j]<=i;j++)ans=max(ans,a[i-B[j]]);
            cout<<ans<<endl;
        }
        all=now;
    }
    return 0;
}

DZY Loves Colors (区间合点线段树)

题意

给出N个点M个操作

每个操作可以把一段区间染色 并且如果一个结点被染色那么他的value会增加abs(new-old)

另一个操作是求区间的value

思路

区间问题首先线段树和分块

都能做 我先说线段树，分块晚上在做

线段树，我们可以每次把一个染色的区间看成一个点，对于一次染色最多把三个区间看成一个结点，也就是logn的复杂度

所以答案就是mlogn

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m;
void read(int &res){
    res=0;
    char c;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
        while(c=getchar(),c>47);
}
inline void out(ll x)
{
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}
struct SegTree{
    struct node{
        int l,r,len,color,mid;
        ll sum,lazy;
    }my[maxn<<2];
    void build(int o,int l,int r){
        my[o].l=l,my[o].r=r,my[o].len=(r-l+1),my[o].mid=(l+r)/2;
        my[o].sum=my[o].lazy=0;my[o].color=-1;
        if(l==r){
            my[o].color=l;
            return;
        }
        int mid=(l+r)/2;
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);
    }
    inline void up(int o){
        my[o].sum=my[o<<1].sum+my[o<<1|1].sum;
        if(my[o<<1].color==my[o<<1|1].color)my[o].color=my[o<<1].color;
        else my[o].color=-1;
    }
    void mix(int o,ll val,int col){
        my[o].lazy+=val;
        my[o].sum+=1LL*my[o].len*val;
        my[o].color=col;
    }
    void down(int o){
        if(!my[o].lazy)return;
        mix(o<<1,my[o].lazy,my[o].color);
        mix(o<<1|1,my[o].lazy,my[o].color);
        my[o].lazy=0;
    }
    void update(int o,int l,int r,int val){
        if(my[o].l>=l&&my[o].r<=r&&~my[o].color){
            mix(o,abs(val-my[o].color),val);
            return;
        }
        int mid=my[o].mid;
        down(o);
        if(l<=mid)update(o<<1,l,r,val);
        if(r>mid)update(o<<1|1,l,r,val);
        up(o);
    }
    ll query(int o,int l,int r){
        if(my[o].l>=l&&my[o].r<=r){
            return my[o].sum;
        }
        down(o);
        int mid=my[o].mid;
        ll ans=0;
        if(l<=mid)ans+=query(o<<1,l,r);
        if(r>mid)ans+=query(o<<1|1,l,r);
        return ans;
    }
}seg;
int main()
{
    read(n);read(m);
    seg.build(1,1,n);
    while(m--){
        int type,l,r,val;
        read(type);
        if(type==1){
            read(l);read(r);read(val);
            seg.update(1,l,r,val);
        }
        else{
            read(l);read(r);
            out(seg.query(1,l,r));
            puts("");
        }
    }
    return 0;
}

Diposting di | Edited on

传送门

A.Anton and Letters (签到)

题意

判断字符串里面有多少个不同字符

思路

直接set一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
set<char>st;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string s;
    getline(cin,s);
    int len=s.size();
    for(int i=0;i<len;i++){
        if(s[i]>='a'&&s[i]<='z')st.insert(s[i]);
    }
    cout<<st.size();
    return 0;
}

B.Kolya and Tandem Repeat (暴力模拟)

题意

给你一个字符串,你可以在末尾添加K个任意字符 ,让你找出一个最长的重复两次的字串

思路

直接暴力模拟

对于每个字串长度,字串起点,开始判断，复杂度n^3

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string ss;
    cin>>ss;
    string s="";s+='*';s+=ss;
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        s+='*';
    }
    int ans=0;
    int len=s.size()-1;
    for(int i=1;i<len;i++){
        for(int j=1;j<len;j++){
            if(i+2*j-1>len)continue;
            int head=i,tail=i+j,flag=0;
            for(int k=1;k<=j;k++){
                if(s[head+k-1]=='*'||s[tail+k-1]=='*'||s[head+k-1]==s[tail+k-1])continue;
                flag=1;
            }
            if(!flag)ans=max(ans,j*2);
        }
    }
    cout<<ans;
    return 0;
}

C.Borya and Hanabi (大模拟,二进制模拟)

题意

现在有五种花色五种数字组成的二十五张牌，你手里有诺干张牌，每次你可以询问一种颜色和一种数字，你会得到所有这个花色/数字牌的位置，问你最少多少次可以把所有的牌分类

思路

把题目抽象成一个二维坐标，花色为横坐标，数字为纵坐标，每次可以连接一条线，把一条线上的牌找到,对于一张牌有两种找到方法，

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int x[maxn];
int y[maxn];
void who(string s,int i){
    char top=s[0];
    if(top=='B')x[i]=0;
    else if(top=='Y')x[i]=1;
    else if(top=='W')x[i]=2;
    else if(top=='G')x[i]=3;
    else x[i]=4;
    y[i]=s[1]-'1';
}
int n;
int bit(int i){return 1<<i;}
bool check (int sta) {
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(x[i]==x[j]){
                if( y[i]!=y[j] && (sta&bit(y[i]+5))==0&& (sta&bit(y[j]+5))==0  )return false;
            }
            else{
                if( (sta&bit(x[i])) || (sta&bit(x[j])) )continue;
                if(y[i]!=y[j] && ((sta&bit(y[i]+5)) || (sta&bit(y[j]+5)) ))continue;
                return false;
            }
        }
    }
    return true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        who(s,i);
    }
    int ans=inf;
    for(int sta=0;sta<(1<<10);sta++){
        //cout<<bitset<11>(sta)<<endl;
        int num=0;
        for(int i=0;i<5;i++){
            if(sta&(1<<i)){
                num++;
            }
            if(sta&(1<<(i+5))){
                num++;
            }
        }
        if(check(sta))ans=min(ans,num);
    }
    cout<<ans<<endl;
    return 0;
}

D.Andrey and Problem（贪心）

题意

你有N个朋友，每个朋友都有百分之a[i]的几率给你出题，你现在只想要一道题，

想知道你选择哪些朋友给只出一题的几率最大，输出最大几率

例如 n=2

a1=0.1 a2=0.2

答案是 0.1×0.8 + 0.9×0.2=0.26

思路

一开始我是直接DP背包的然后发现错了，结果答案直接排序一下，暴力枚举就行了，我也不知道怎么证明…感觉很奇怪

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=5e4+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
double dp[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    double yes,no;
    for(int i=1;i<=n;i++)cin>>dp[i];
    sort(dp+1,dp+1+n,[](double a,double b){
         return a>b;});
    yes=dp[1],no=1.0-dp[1];
    for(int i=2;i<=n;i++){
        double nowyes,nowno;
        nowyes=dp[i]*(no)+(1-dp[i])*(yes);
        if(nowyes>yes){
            yes=nowyes;
            no=no*(1-dp[i]);
        }
    }
    cout<<fixed<<setprecision(10);
    cout<<yes;
    return 0;
}

E.Artem and Array (模拟栈，贪心)

题意

给你N个数,这N个数相邻，你每次可以删除一个数，然后得到这个数周围两个数的最小值，（如果有一边没有数字只能获得零值）让你求把这N个数全部删除的值

思路

在纸上模拟一下，如果要最优那就是一开始把小的都删除(等于的也要删除)，最后留下的都是比较大的，会发现留下的数组是一个先递增再递减的数组，并且最大和第二大的值是相邻的无法取到，所以答案就是前面删除获取的值和后面剩下的数组的前n-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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n;
ll a[maxn];
ll ans;
ll st[maxn];
int top=0;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        ll x;
        cin>>x;
        while(top>=2&&st[top-1]>=st[top]&&x>=st[top]){
            ans+=min(st[top-1],x);
            top--;
        }
        st[++top]=x;
    }
    sort(st+1,st+top+1);
    for(int i=1;i<=top-2;i++){
        ans+=st[i];
    }
    cout<<ans<<endl;
    return 0;
}

Diposting di | Edited on

传送门

今天我的问题：
1：没有看D，一眼认为D是大模拟题，就不做了，(其实D只是个DP而且我是可以切掉的)
2：不去做I题，其实I题我有基本思路但是我的想法代码量太大。（太懒)
3：梦游太久，没有及时去开新题。坐等翻译
4：C题没想清楚就上了，后面发现自己没有大数快速幂板子，浪费时间

D. Match Stick Game

D这题是真特么可以做得出来，学弟让我做 我第一眼看到图，以为是个大模拟，我操 结果赛后一发AC fuck

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
#define bug cout<<"hello"<<endl;

int num[maxn];
///        0 1 2 3 4 5 6 7 8 9
int a[50]={6,2,5,5,4,5,6,3,7,6};

ll mx[20][150],mi[150][20];///几位用了几根;
ll dp[200][1000];///前几个数字用了多少根
void init(){
    for(int i=1;i<20;i++)
    for(int j=0;j<150;j++){
        mx[i][j]=-1e18,mi[i][j]=1e18;
    }
    mx[0][0]=mi[0][0]=0;
    for(int i=0;i<20;i++){
        for(int j=0;j<150;j++){
            for(int k=0;k<=9;k++){
                int ned=a[k];
                if(i==0&&k==0)continue;
                if(mx[i][j]!=-1e18){
                    mx[i+1][j+ned]=max(mx[i+1][j+ned],mx[i][j]*10+k);
                }
                if(mi[i][j]!=1e18){
                    mi[i+1][j+ned]=min(mi[i+1][j+ned],mi[i][j]*10+k);
                }
            }
        }
    }
   // cout<<mx[1][2]<<endl;
   // cout<<mx[1][7]<<endl;
}


int main()
{
    init();
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string s;
        cin>>s;
        int cnt=0;
        int k=1;
        memset(num,0,sizeof(num));
        for(int i=0;i<n;i++){
            if(s[i]=='-'){
                cnt++;
                ++k;
            }
            else if(s[i]=='+'){
                cnt+=2;
                ++k;
            }
            else{
                cnt+=a[s[i]-'0'];
                num[k]++;
            }
        }
        for(int i=0;i<=n+10;i++){
            for(int j=0;j<1000;j++){
                dp[i][j]=-1e18;
            }
        }
       // cout<<"cnt="<<cnt<<endl;
        dp[0][0]=0;
        for(int i=1;i<=k;i++){
            if(i==1){
                for(int j=1;j<=cnt;j++){
                    for(int len=1;len<100&&len<=j;len++){
                        if(dp[i-1][j-len]!=-1e18&&mx[num[i]][len]!=-1e18){
                            dp[i][j]=max(dp[i][j],dp[i-1][j-len]+mx[num[i]][len]);
                           // cout<<"a[i]="<<num[i]<<" len="<<len<<endl;
                          //  cout<<"mx[a[i][len]="<<mx[num[i]][len]<<endl;
                          //  cout<<"a[i]="<<num[i]<<endl;
                        }
                    }
                }
            }
            else{
                for(int j=1;j<=cnt;j++){
                    for(int len=1;len<100;len++){
                        if(len+2<=j&&dp[i-1][j-len-2]!=-1e18&&mx[num[i]][len]!=-1e18){
                            dp[i][j]=max(dp[i][j],dp[i-1][j-len-2]+mx[num[i]][len]);
                        }
                        if(len+1<=j&&dp[i-1][j-len-1]!=-1e18&&mi[num[i]][len]!=1e18){
                            dp[i][j]=max(dp[i][j],dp[i-1][j-len-1]-mi[num[i]][len]);
                        }
                    }
                }
            }
        }
        cout<<dp[k][cnt]<<endl;
    }
    return 0;
}

I. Max answer

单调栈处理出 左边界和右边界，然后贪心选取前缀和差分一下。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+50;
#define bug cout<<"hello"<<endl;
int ls[maxn],rs[maxn];
ll sum[maxn];
int a[maxn];

stack<int>st;

ll mx[maxn<<2],mi[maxn<<2];

void build(int o,int l,int r){
    if(l==r){
        mx[o]=sum[l];
        mi[o]=sum[r];
        return;
    }
    int mid=(l+r)/2;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    mx[o]=max(mx[o<<1],mx[o<<1|1]);
    mi[o]=min(mi[o<<1],mi[o<<1|1]);
}
ll querymi(int o,int l,int r,int ql,int qr){
  //  cout<<"o="<<o<<endl;
    if(ql<=l&&qr>=r){
        return mi[o];
    }
    int mid=(l+r)/2;
    ll ans=1e18;
    if(ql<=mid)ans=min(ans,querymi(o<<1,l,mid,ql,qr));
    if(qr>mid)ans=min(ans,querymi(o<<1|1,mid+1,r,ql,qr));
    return ans;
}
ll querymx(int o,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r){
        return mx[o];
    }
    int mid=(l+r)/2;
    ll ans=-1e18;
    if(ql<=mid)ans=max(ans,querymx(o<<1,l,mid,ql,qr));
    if(qr>mid)ans=max(ans,querymx(o<<1|1,mid+1,r,ql,qr));
    return ans;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    build(1,0,n);
    a[0]=a[n+1]=-1e9;
    st.push(0);
    for(int i=1;i<=n;i++){
        while(!st.empty()&&a[st.top()]>=a[i])st.pop();
        ls[i]=st.top();
        st.push(i);
    }
    while(!st.empty())st.pop();
    st.push(n+1);
    for(int i=n;i;i--){
        while(!st.empty()&&a[st.top()]>=a[i])st.pop();
        rs[i]=st.top();
        st.push(i);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        int l1=ls[i],r1=i-1;
        int l2=i,r2=rs[i]-1;
        if(a[i]<0){
            ans=max(ans,a[i]*(querymi(1,0,n,l2,r2)-querymx(1,0,n,l1,r1)));
        }
        else{
            ans=max(ans,a[i]*(querymx(1,0,n,l2,r2)-querymi(1,0,n,l1,r1)));
        }
    }
    cout<<ans<<endl;
    return 0;
}

Diposting di | Edited on

B 升级超梦 (dfs)

思路

题目比较简单，每一回合只有两个情况 要么用经验 要么用糖果

所以我们直接搜索一下n个糖果和m个exp的情况

即$dp[n][exp]=max(dp[n][exp-need],dp[n-1][exp])$

D Bella 姐姐发辣条 (二分)

思路

我们发现只要最后一个人的辣条数确定了那全部人的辣条就确定了。

而且总答案随着最后一个人的辣条数减少而减少 。所以符合二分性

E 禁忌的共鸣 (数论+最小生成树)

思路

首先需要看出题目要求的是一个最大生成树

如果两个结点之间相连肯定答案是他们是GCD也就是他们的因子值

所以我们预处理每个数的因子，然后从最大的因子开始建立生成树

F zzh 与同余方程 (数论)

思路

首先$b-a=km$ 带入$(i+1)^{i+1}=(i+1)^i$ 可以得到$(i+1)^{i+1}-(i+1)^i=(i+1)^{i} \times(i)$

题目要求的就是$\sum (i+1)^i\times(i)$ 设$f[n]=(i+1)^i$ $g[n]=i$

我们可以很轻松预处理出$i+1$的因子然后发现$(i+1)^i$ 和$i+1$之间有种关系

假设$i+1=prime1^a \times prime2^b \times prime3^c \dots$ 那么$(i+1)^i=(prime1^a \times prime2^b \times prime3^c)^i$

所以根据求因子公式$ (a+1)(b+1)(c+1)$得出$(a\times t+1)(b\times t +1)(c \times t + 1)$

因为因子数是积性函数 并且$i和i+1$互质

所以答案就很显然了。

H Draw 顺小王子 (爆搜+模拟)

思路

暴力搜索的复杂度为$49^2 \times T\times13$

所以绰绰有余，主要是这题模拟的细节处理

K wjj 的自动售货机 (线段树区间取模)

思路

第一眼线段树，区间取模和求和都明显了。

Diposting di | Edited on

gcd

$gcd(n,m)=gcd(m,n \%m)$

一个常识

如果$a\leq b$ 并且$b\leq a$那么$a=b$

一个引理

假设$k|a,k|b$ 则对于任意的$x,y属于z，k|(xa+yb)$ 均成立

证明：

$k|a \to a=pk$ $k|b \to b=qk$

于是有$xa+yb=xpk+yqk=(xp+yq)k$

因为$k|(xp+yq)k$所以$k|(xa+yb)$

gcd的Euclid证明

证明：

令$k=gcd(n,m)$ 则$k|n$并且$k|m$

令$j=gcd(m,n\%m)$ 则$j|m$并且$j|(n \%m) $

对于$n$ 可以用$m$表示为$n=p\times m +n\%m$

由引理可知$j|n$(其中$x=p,y=1$),又$j|m$ 于是$j是n和m的公因数(但补一定最大)$

因为$k$是$m和n的最大公因数$ 所以$j\leq k$

通过另一种方式得到$n\%m=n-p\times m$

所以$k$是$n\%m$的因子,又$k|m$。于是$k是n\%m和m的公因子$ (但不是最大)

又$j>=k$ 所以$j==k$

所以$gcd(n,m)=gcd(m,n\%m)$

exgcd

求方程$ax+by=gcd(a,b)$的一个解

如果$b=0$ 那么$gcd(a,b)=a,取x=1,y=0$即可

否则：根据$gcd(a,b)=gcd(b,a\%b)$

那么递归求解$ bx+a\%by=gcd(a,b)$的解

然后推当前$x,y$

设$bx+a\%by=gcd(a,b)$的解为$x0,y0$

$ax+by=gcd(a,b)=bx0+a\%by$

$=bx0+(a-a/b\times b)y0$

$=bx0+ay0-a/b\times b y0$

$=ay0+b(x0-a/b \times y0)$

所以$x=y0,y=x0-a/b\times y0$

Diposting di | Edited on

hzy 和zsl 的生存挑战 （签到）

我还是要吐槽一下，题目都说了两人没有交流还怎么能推出一个人相同一个人不相同，如果两个人都相同呢？

1
2
3
puts("1.00\n1.00\n1.00\n1.00");
    return 0;
}

人类史上最大最好的希望事件 （矩阵快速幂求fib前缀平方和）

思路

斐波那契数列前n项和答案为$F_{N}*F_{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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=192600817;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

ll x,y;
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat& A,mat &B){
    mat C(A.size(),vec(B[0].size()));
    for(int i=0;i<A.size();i++)
        for(int k=0;k<B.size();k++)
        if(A[i][k])
            for(int j=0;j<B[0].size();j++)
            C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
    return C;
}
mat Pow(mat A,ll n){
    mat B(A.size(),vec(A.size()));
    for(int i=0;i<A.size();i++)B[i][i]=1;
    for(;n;n>>=1,A=mul(A,A))
        if(n&1)B=mul(B,A);
    return B;
}
int main(){
    int q;
    while(~scanf("%d",&q)){
        for(int i=1;i<=q;i++){
            ll a,b,c,d;
            scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
            a=a*4+b+1;b=c*4+d+1;
            if(a>b)swap(a,b);
            a--;
            mat A(2,vec(2)),B(2,vec(2)),F1(2,vec(1)),F2(2,vec(1));
            A[0][0]=A[0][1]=A[1][0]=1;A[1][1]=0;
            F1[0][0]=1;F1[1][0]=0;
            B[0][0]=B[0][1]=B[1][0]=1;B[1][1]=0;
            F2[0][0]=1;F2[1][0]=0;
            A=Pow(A,a);
            B=Pow(B,b);
            F1=mul(A,F1);
            F2=mul(B,F2);
            ll ans1=F1[0][0]*F1[1][0]%mod;
            ll ans2=F2[0][0]*F2[1][0]%mod;
            printf("%lld\n",(ans2-ans1+mod)%mod);
        }
    }
    return 0;
}

超级无敌简单题 (规律)

思路

发现如果出现4就会出现死循环

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e8+7;
const int maxn=5e5+50;
const int inf=1e8;
vector<int>ve;
bool isok(int n){
    while(n!=1&&n!=4){
        ll sum=0;
        while(n){
            sum+=(n%10)*(n%10);
            n/=10;
        }
        n=sum;
    }
    return n==1;
}
int main()
{
    int q;
    for(int i=1;i<1100000;i++){
        if(isok(i))ve.push_back(i);
    }
    //cout<<ve.size()<<endl;
    /*for(int i=0;i<ve.size();i++){
        cout<<ve[i]<<endl;
    }*/
    scanf("%d",&q);
    while(q--){
        int n;
        scanf("%d",&n);
        printf("%d\n",ve[n-1]);
    }
    return 0;
}

免费送气球 (权值线段树)

思路

对于每个数存一个数量和val 然后判断数量是否大于查询数量，

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>
using namespace std;
typedef long long ll;
const ll inf=1e16;
const ll mod=1e9+7;
const int maxn=1e5+50;

ll sum[maxn*40],val[maxn*40];
int ls[maxn*40],rs[maxn*40];
int cnt;
void update(int &o,int l,int r,int k,int num){
    if(!o)o=++cnt;
    sum[o]+=k;
    val[o]+=1LL*k*num;
    val[o]%=mod;
    if(l==r)return;
    int mid=(l+r)/2;
    if(num<=mid)update(ls[o],l,mid,k,num);
    else update(rs[o],mid+1,r,k,num);
}
ll query(int o,int l,int r,ll k){
    if(l==r)return 1LL*k*l%mod;
    int mid=(l+r)/2;
    ll res=0;
    if(k>sum[ls[o]])res=(val[ls[o]]+query(rs[o],mid+1,r,k-sum[ls[o]]));
    else res=query(ls[o],l,mid,k);
    return res%mod;
}


int main()
{
    int q,rt=0;
    cin>>q;
    while(q--){
        int op;ll l,r;
        cin>>op>>l>>r;
        if(op==1)update(rt,0,1e9,l,r);
        else{
            cout<<(query(rt,0,1e9,r)-query(rt,0,1e9,l-1)+mod)%mod<<endl;
        }
    }
    return 0;
}

简单数学题 (数学题)

思路

$F(n) = \sum_{i=1}^n (i \times \sum_{j=i}^n C_j^i)$

->$F(n)=\sum_{i=1}^{n}\sum_{j=i}^{n} i \times C_{j}^{i} $

其中$ \sum C_{j}^{i}$ 是杨辉三角的一条斜线

然后把i乘入这个斜线中，发现杨辉三角变成一个新的少了一维的杨辉三角

发现新的杨辉三角是之前的杨辉三角每一层的元素乘上层号

然后就是变成求$\sum_{i=1}^{n} i\times 2^{i-1}$

$1\times 2+2 \times2^1 +3 \times 2^2+\dots n \times2^{n-1}$

然后拆项为

根据等比数列$s_n=\frac{a_1(1-a_n)}{1-q}=\frac{a_nq-a_1}{q-1}$

整理

第一行变成$2^n-2^0$ 第二行变成$2^n-2^1$ 第n行变成$2^n-2^{n-1}$

再整理变成$n\times2^n-(2^n-1)=(n-1)\times2^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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int maxn=5e5+50;
const int inf=1e8;
ll ksm(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll n;
    while(~scanf("%lld",&n)){
        ll ans=ksm(2,n);
        n%=mod;
        ans=(ans*(n-1))%mod;
        ans+=1;ans%=mod;
        printf("%lld\n",ans);
    }
    return 0;
}

zyb的面试 (原题)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int maxn=1e3+50;
const ll inf=1e17;
int cal(int n,int k){
    int cur=1;
    k=k-1;
    while(k>0){
        int step=0,first=cur,last=cur+1;
        while(first<=n){
            step+=min(n+1,last)-first;
            first*=10;
            last*=10;
        }
        if(step<=k){
            cur++;
            k-=step;
        }
        else{
            cur*=10;
            k-=1;
        }
    }
    return cur;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        cout<<cal(n,k)<<endl;
    }
    return 0;
}

Count (矩阵快速幂)

思路

考虑矩阵快速幂 考虑要从前一项得到后一项的$n^3$

根据公式$(n+1)^3=n^3+3n^2+3n+1$

推出$f(n)=f(n-1)+2f(n-2)+n^3+3n^2+3*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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=123456789;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
#define bug cout<<"here"<<endl;
typedef vector<ll>vec;
typedef vector<vec>mat;

mat mul(mat& A,mat &B){
    mat C(A.size(),vec(B[0].size()));
    for(int i=0;i<A.size();i++)
        for(int k=0;k<B.size();k++)
        if(A[i][k])
            for(int j=0;j<B[0].size();j++)
            C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
    return C;
}
mat Pow(mat A,ll n){
    mat B(A.size(),vec(A.size()));
    for(int i=0;i<A.size();i++)B[i][i]=1;
    for(;n;n>>=1,A=mul(A,A))
        if(n&1)B=mul(B,A);
    return B;
}

int main(){
    int q;
    scanf("%d",&q);
    while(q--){
        ll n;
        scanf("%lld",&n);
        if(n==1){
            printf("1\n");continue;
        }
        else if(n==2){
            printf("2\n");continue;
        }
        mat a(6,vec(6));
        a[0][0]=1;a[0][1]=2;a[0][2]=1;a[0][3]=3;a[0][4]=3;a[0][5]=1;
        a[1][0]=1;a[1][1]=0;a[1][2]=0;a[1][3]=0;a[1][4]=0;a[1][5]=0;
        a[2][0]=0;a[2][1]=0;a[2][2]=1;a[2][3]=3;a[2][4]=3;a[2][5]=1;
        a[3][0]=0;a[3][1]=0;a[3][2]=0;a[3][3]=1;a[3][4]=2;a[3][5]=1;
        a[4][0]=0;a[4][1]=0;a[4][2]=0;a[4][3]=0;a[4][4]=1;a[4][5]=1;
        a[5][0]=0;a[5][1]=0;a[5][2]=0;a[5][3]=0;a[5][4]=0;a[5][5]=1;
        mat f(6,vec(1));
        f[0][0]=2;
        f[1][0]=1;
        f[2][0]=8;
        f[3][0]=4;
        f[4][0]=2;
        f[5][0]=1;
        a=Pow(a,n-2);
        f=mul(a,f);
        printf("%lld\n",f[0][0]);
    }
    return 0;
}