Codeforces Round #705 (Div. 2)

A、Anti-knapsack

题意：
给我们一个n，一个k(n,k<=1000)，需要我们得到一个集合，集合的元素全部小于n，并且任意子集相加不等于k，而且这个集合元素相加尽可能大。

思路：
大于 $k$ 的数全取，小于的 $k$ 的数只能取一半，所以取大的一半。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
typedef long long int ll;
#define eb emplace_back
#define ef emplace_front
#define ep emplace
#define fi first
#define se second
inline void solve() {
    int n,k;
    cin>>n>>k;
    int l=(k+1)>>1;
    if(n-l) {
        cout<<n-l<<'\n';
        for(int i=l;i<k;++i) cout<<i<<' ';
        for(int i=k+1;i<=n;++i) cout<<i<<' ';
        cout<<'\n';
    }
    else cout<<0<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) solve();
}

B、 Planet Lapituletti

题意：
某个星球上的时间和我们地球类似，但是每天有h个小时，每小时有m分钟（1<=h,m<=100）。当前时间为HH:MM，这时候有一面镜子，问从HH:MM开始往后，当镜子里的时间合理时，即镜子里的时间满足0<=H<h && 0<=M<m时（镜子里的时间是当前时间的反射），真实时间是多少，以HH:MM格式输出。

思路：
模拟

MyCode:

#include <bits/stdc++.h>
using namespace std;
int h,m;
int mp[10]={0,1,5,-1,-1,2,-1,-1,8,-1};
inline bool check(const vector<int> &a, const vector<int> &b) {
    if(mp[a[1]]==-1||mp[a[0]]==-1||mp[b[0]]==-1||mp[b[1]]==-1) return false;
    int hh=mp[a[1]]*10+mp[a[0]],mm=mp[b[1]]*10+mp[b[0]];
    if(hh>=h||mm>=m) return false;
    return true;
}
inline void solve() {
    int hh,mm;
    scanf("%d%d",&h,&m);
    scanf("%d:%d",&hh,&mm);
    vector<int>a(2),b(2);
    while(1) {
        for(int i=hh,j;i<h;++i) {
            for(j=mm;j<m;++j) {
                a[0]=i/10,a[1]=i%10;
                b[0]=j/10,b[1]=j%10;
                if(check(b,a)) {
                    printf("%02d:%02d\n",i,j);
                    return;
                }
            }
            mm=0;
        }
        hh=0;
    }
}
int main() {
    int T;    scanf("%d",&T);
    while(T--) solve();
}

C、K-beautiful Strings

题意：
给我们一个由小写字母组成的字符串S，长度为n（n<=1e5），然后给我们一个k（k<=n）,要我们找出比字典序尽可能小但不小于 S 的字符串，这个字符串还需满足每种字母出现的个数都是k的倍数。

思路：
当字符串长度n不是k的倍数的时候，不存在这种字符串
当字符串s满足条件时，s就是需要求的字符串
在修改字符串s的一些字符串从而得到需要的字符串时，开始修改的部位一定越靠后越好，这样得到的字符串才能最小。用桶存每个字母出现的次数，从大到小枚举修改的部分 $(i\sim n)$ ，计算还需要修改几(假设需要修改sum个位置)个位置才能使 $1\sim i-1$ 的字母的出现次数是k的倍数，同时用que保存出现次数不是k的倍数的字母。如果sum小于 $n-i+1$ ，那么就得不到需要的字符串。用nex数组维护每个字母还需要加几个才能凑齐k的倍数
情况一：当 $sum<=n-i+1$ 时，如果出现次数不是k的倍数的字母中最大的字母x大于s[i]，那么直接把s[i]改成que中第一个大于s[i]的字母，同时修改这个字母的nex数组，以及sum--，表示已经修改了一次了；
情况二：当 $sum<n-i+1$ 时，因为n是k的倍数，所以此时 $sum+k<n-i+1$ ，也就是说我可以构造k个 $s[i]+1$ ，所以直接把s[i]改成s[i]+1，同时修改s[i]+1的nex数组，以及sum--，需要注意的是，可能s[i]+1的nex数组已经是k的倍数了，所以如果此时 $--nex[s[i]-'a'+2]$ 可能会是负数，如果减成了负数，那么 $nex[s[i]-'a'+2]+=k,sum+=k$ 即可。
优先判断情况二（保证求得的字符串最小），处理完情况一或情况二后，把多余的字母修改成'a'，然后从小到大修改成需要增加的字母。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=2e5+7;
typedef long long int ll;
#define eb emplace_back
#define ef emplace_front
#define ep emplace
#define fi first
#define se second
int n,k,cnt[30],que[30],nex[30],tot,sum;
char s[maxn];
inline bool check(int r) {
    sum=tot=0;
    for(int i=1; i<=26; ++i) if(cnt[i]%k) {
            sum+=k-cnt[i]%k;
            que[++tot]=i;
        }
    return sum<=n-r+1;
}
inline void print(int r) {
    for(int i=1; i<=r; ++i) printf("%c",s[i]);
}
int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);

    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&k);
        scanf("%s",s+1);
        if(n%k) {
            puts("-1");
            continue;
        }
        for(int i=1; i<=26; ++i) cnt[i]=0;
        for(int i=1; s[i]; ++i) cnt[s[i]-'a'+1]+=1;
        if(check(n+1)) {
            print(n);
            putchar('\n');
            continue;
        }
        for(int i=n; i; --i) {
            cnt[s[i]-'a'+1]-=1;
            if(s[i]=='z') continue;
            if(check(i) && (que[tot] > s[i]-'a'+1 || sum < n-i+1)) {
                print(i-1);
                for(int j=1; j<=26; ++j) if(cnt[j]%k) nex[j]=k-cnt[j]%k;
                    else nex[j]=0;
                if(sum < n-i+1) {
                    printf("%c",s[i]+1);
                    --nex[s[i]-'a'+2],--sum;
                    if(nex[s[i]-'a'+2]<0) nex[s[i]-'a'+2]+=k,sum+=k;
                } else {
                    for(int j=s[i]-'a'+2; j<=26; ++j) {
                        if(nex[j]) {
                            printf("%c",j+'a'-1);
                            --nex[j],--sum;
                            break;
                        }
                    }
                }
                nex[1]+=n-i-sum;
                for(int j=1; j<=26; ++j) {
                    while(nex[j]--) printf("%c",(char)(j-1+'a'));
                }
                putchar('\n');
                break;
            }
        }
    }
}

D、GCD of an Array

题意：
给一个数列，m次操作，每次将pos位置的数乘上x，问每次操作后数列的总gcd

思路：
求数列的总gcd会想到分解质因数，每个位置共有的质因数乘以这个质因数的最小个数，就是他们的总gcd。
将pos位置的数乘上x，其实就是给pos位置增加因子x，分解出x内的质因数，算贡献。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=4e4+7,mod=1e9+7;
#define eb emplace_back
int pre[maxn],prime[maxn],rev[maxn];
int n,ans=1;
unordered_map<int,int>mp[maxn];
vector<int>v[maxm];
inline void add(int x,int val) {
    int t,y;
    while(val!=1) {
        t=pre[val];//先筛出最小的质因数 
        val/=t;
        t=rev[t];//离散化 
        y=mp[x][t]++;//y+1表示 a[x]质因数t的个数
        if(y==v[t].size())  v[t].emplace_back(0);//质因子t的最大个数增加，则新开一维去统计 
        if(++v[t][y]==n) ans=ans*1LL*prime[t]%mod;//又凑齐n个质因子t，最大公约数*t 
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i=2,tot=0;i<maxn;++i) {
        if(!pre[i]) {
            prime[++tot]=pre[i]=i;
            rev[i]=tot;
        }
        for(int j=1;j<=tot&&i*prime[j]<maxn;++j) {
            pre[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
    int Q,x,val;
    cin>>n>>Q;
    for(int i=1;i<=n;++i) {
        cin>>x;
        add(i,x);
    }
    while(Q--) {
        cin>>x>>val;
        add(x,val);
        cout<<ans<<'\n';
    }
}

E、Enormous XOR

题意：
n是二进制串的长度
第一行是L的二进制表示
第二行是R的二进制表示

$g(x,y)=x\ XOR(x+1)\ XOR\ ...\ XOR\ (y-1)\ XOR\ y$

$f(L,R)=max(\ g(x,y)\ ),L\le x\le y\le R$

思路：
最差的情况就是取x=y=R，答案就是R

结论一：若L和R的最高位相同，那么答案为11...11
我只要取x=01...11,y=10...00即可。

结论二：若L和R最高位相同，R为奇数，答案是R
不会证

结论三：若L和R最高位相同，R为偶数，且 $R-2>=L$ ，答案是R+1，反之是L
我只要取R、R-1、R-2就可以得到R+1

MyCode:

#include <bits/stdc++.h>
using namespace std;
int n,pos;
string l,r;
string add(string s) {
    pos=n-1;
    while(s[pos]=='1') {
        s[pos]='0';
        --pos;
    }
    s[pos]='1';
    return s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    cin>>l>>r;
    if(l[0]!=r[0]) {
        string c(n,'1');
        cout<<c<<'\n';
        return 0;
    }
    if(l==r||r[n-1]=='1'||add(l)==r)
        cout<<r<<'\n';
    else cout<<add(r)<<'\n';
}