首页 > 其他分享 >Codeforces 708 A-E1题解

Codeforces 708 A-E1题解

时间：2023-01-27 04:55:08浏览次数：51  
标签：708 int 题解 ll long ans E1 rep define

A. Meximization

这道题问给一些数，如何让前缀的mex之和最大，那么首先，我们要抬mex的话肯定是要把前面都铺垫完的，所以在i位置确定的时候，i + 1自然是越大越好，可以证明i + 1的位置放大至少优于放小，然后其他数搞一搞就行

AC Code 
#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].nxt)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;

inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
ll inv(ll x){
    return quick_pow(x, mod - 2);
}
ll C(ll n, ll m){
    ll ans = 1;
    for(ll i = 1; i <= m; i++){
        ans = ans * (n - i + 1) % mod;
        ans = ans * inv(i) % mod;
    }
    return ans;
}
int n,m;
int a[limit];
void solve(){
    cin>>n;
    map<int, int>mp;
    rep(i,1,n) cin>>a[i];
    int it = 0;
    sort(a + 1, a + 1 + n);
    vector<int>v;
    rep(i,1,n){
        if(!mp[a[i]]) mp[a[i]]++, cout<<a[i]<<" ";
        else v.push_back(a[i]);

    }
    for(auto x : v) cout<<x<<" ";
    cout<<endl;
};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
    invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

B. M-arrays

这道题问的是给一个数列和一个数m，要求选若干组，每组相邻的元素之和可以被m整除，问最少要分多少组

首先我们可以只关心m的余数，然后我们枚举余数i从1-m -1，然后我们可以知道i的数量和m - i的数量，这两个可以凑成符合要求的数字

然后假如有x个i，y个m - i，x < y， 那么x个i最多能带走x + 1个y，然后剩下的y，如果有的话，单独加出来就行

最后要注意特殊处理一下0，显然无论多少个0加起来都是符合要求的，所以 + 1

AC Code 
#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].nxt)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;

inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
ll inv(ll x){
    return quick_pow(x, mod - 2);
}
ll C(ll n, ll m){
    ll ans = 1;
    for(ll i = 1; i <= m; i++){
        ans = ans * (n - i + 1) % mod;
        ans = ans * inv(i) % mod;
    }
    return ans;
}
int n,m;
int a[limit];
void solve(){
    cin>>n>>m;
    map<int, int>mp;
    rep(i,1,n)cin >> a[i], a[i] %= m, mp[a[i]]++;
    int ans = 0;
    rep(i, 1, m  / 2){
        int fst = mp[i];
        int scd = mp[m - i];
        if(fst > scd) swap(fst, scd);
        if(!fst){
            ans += scd;
        }else{
            scd -= fst + 1;
            ++ans;
            ans += max(0, scd);
        }

    }
//    ans >>= 1;
    if(mp[0])ans += 1;
    cout << ans << endl;
};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
    invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

C. k-LCM (easy version) + (hard version)

这题是给一个数字n和一个数字k，要求把数字分解成k个正整数，使得

  • a1 + ... + ak == n
  • lcm(a) <= n / 2

然后easy version是固定k = 3.

那么这个题稍加观察我们发现，其实就是个奇偶题

对于奇数，我们可以分解成1 ， (n - 1) / 2, (n - 1) / 2

那么偶数有两种情况

  • n / 2之后是奇数，那么我们可以从两个n / 2各拆一个1给第一个数字
  • n / 2之后是偶数，那么我们可以让前两个数字相等，也就是n / 2 / 2(n / 2)， 然后再加一个n /2

没什么难度

然后这个hard version如果你写了easy version应该问题就不大，我们只需要先凑m - 3个1（因为1不会对lcm造成负面影响），然后n - m + 3就成功转化为了easy version

AC Code 
#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].nxt)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;

inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
ll inv(ll x){
    return quick_pow(x, mod - 2);
}
ll C(ll n, ll m){
    ll ans = 1;
    for(ll i = 1; i <= m; i++){
        ans = ans * (n - i + 1) % mod;
        ans = ans * inv(i) % mod;
    }
    return ans;
}
int n,m;
int a[limit];
void solve(){
    cin>>n>>m;
    if(n == m){
        rep(i,1,n){
            cout<<1<<" ";
        }
        cout<<endl;
        return;
    }
    if(m > 3){
        n -= m - 3;
        rep(i,1,m - 3){
            cout<<1<<" ";
        }
    }

    if(n & 1){
        cout<<1<<" ";
        --n;
        cout<<n / 2<<" "<<n / 2<<endl;
    }else{
        if(n % 4 == 0){
            cout<<n / 4<<" ";
            cout<<(n / 4)<<" "<<(n / 2)<<endl;
        }else{
            cout<<2<<" "<<(n / 2 - 1)<<" "<<(n / 2 - 1)<<endl;
        }

    }
};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
    invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

D. Genius

看了下，感觉题应该是属于dp，但是我没想到什么方法可以快速处理2 ^ i，太大了，所以看道E1容易点先去做了。等会儿补一下。

E1.Square-Free Division (easy version)

这个题要把数组分成连续的段，使得段中任意两个元素乘积都不是完全平方数，问最少分段。

这个题肯定是贪心没得跑。

说到完全平方数，就是说所有的质因子数量都是偶数，然后我们分解一下，把奇数分子单列出来，然后排序后给凑成一个字符串，如果有相同的，那么说明已经出现的段内和当前的数字互补，能够形成完全平方数，需要分段。

然后string tle了，我然后试了试整数乘法，可以，但是还是会t。那么预处理这个值呢？1e7的还没处理完就tle了，我真的会谢。那就加个map存fact的结果吧，然后优化了一大圈，请出来了平板电视里的gp_hash_table才过，艰难。

AC Code 
#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].nxt)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;

inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
ll inv(ll x){
    return quick_pow(x, mod - 2);
}
ll C(ll n, ll m){
    ll ans = 1;
    for(ll i = 1; i <= m; i++){
        ans = ans * (n - i + 1) % mod;
        ans = ans * inv(i) % mod;
    }
    return ans;
}


int n,m;
int a[limit];
#include <bits/extc++.h>
using namespace __gnu_pbds;
gp_hash_table<ll, ll>dp;

ll fact(ll x){
    ll xx = x;
    if(dp.find(x) != dp.end()) return dp[x];
    map<ll, int>mp;
    for(ll i = 2; i * i <= x; i++){
        ll& px = x;
        if(px % i == 0){
            while(px % i == 0){
                px /= i;
                mp[i]++;
            }
        }
    }
    if(x > 1) mp[x]++;
    ll ans = 1;
    for(auto && [k, v] : mp){
        if(v & 1)ans *= k;
    }
    return dp[xx] = ans;
}
ll b[limit];
void solve(){
    cin>>n>>m;
    rep(i,1,n){
        cin>>a[i];
        b[i] = fact(a[i]);
    }
    unordered_set<ll>st;
    int ans = 1;
    rep(i,1,n){
        if(st.count(b[i])){
            ++ans;
            st.clear();
            st.insert(b[i]);
        }else{
            st.insert(b[i]);
        }
    }
    cout<<ans<<endl;

};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
//    get_prime();

    int kase;
    cin>>kase;
    while (kase--)
    invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

标签：708,int,题解,ll,long,ans,E1,rep,define
From： https://www.cnblogs.com/tiany7/p/17068493.html

相关文章

  • Atcoder ABC244E - King Bombee 题解
    原题：AtcoderABC244E-KingBombee题意给你一张图，从\(S\)到\(T\)，经过\(k\)条边，经过\(X\)号点偶数次的方案数。做法设\(f_{i,j,k}\)表示经过\(i\)条边，......
  • IE10下Session丢失问题接军
    近日使用JQuery完成一个项目，开发环境测试了FF、Chrome、IE10，都工作正常，放到服务器（windows  server2008 r2）上，在客户端FF、Chrome上浏览都没问题，在IE10下，出现问题：登录进去......
  • 【已解决】Error: could not open `C:\Program Files\Java\jre1.8.0_121\lib\amd
    原因：java升级时，会在环境变量的path路径中增加以下两条路径，与我们安装java的路径重合。解决方法：删掉环境变量中的这两条语句，同时找到对应文件，删除即可。C:\ProgramData\O......
  • 洛谷 P1208混合牛奶 题解
    一道贪心算法不是很明显的题目，其实一般的递推也可以做。 大体思路：肯定优先购买单价最低的奶农的牛奶，那么就需要先根据牛奶单价进行排序，这里用结构体会更好一点。之后在......
  • 【算法训练营day25】LeetCode216. 组合总和III LeetCode17. 电话号码的字母组合
    LeetCode216.组合总和III题目链接：216.组合总和III独上高楼，望尽天涯继续复健，一直在犯小的语法错误。慕然回首，灯火阑珊和昨天的题很像，主要区别在于递归返回条件和回溯......
  • CF1780 F.Three Chairs - 题解
    给定数列\(\{a_n\}\)，求无序三元组\((i,j,k)\)的数量，满足\(\gcd(\min(a_i,a_j,a_k),\max(a_i,a_j,a_k))=1\)，\(n\leq3\cdot10^5,a_i\leq3\cdot10^......
  • ajax跨域访问的问题解决
    在web项目中经常用到在ajax中进行跨域访问，比如在a域中访问b域中的服务，却实现不了。原因是：浏览器为了保证服务器数据的安全，对于这种请求，所给予的权限是较低的，通常只允许调用......
  • QQZone1 - 需求分析&数据库设计
    1.熟悉QQZone业务需求1)用户登录2)登录成功，显示主界面。左侧显示好友列表；上端显示欢迎词。如果不是自己的空间，显示超链接：返回自己的空间；下端显示日志列表3)查看日志......
  • 题解 CF1780G【Delicious Dessert】
    SAM板子题。在P3804【模板】后缀自动机(SAM)中，我们已经会求每个等价类（SAM状态）在原串中的出现次数。本题中，我们需要求所有长度能被出现次数整除的子串。我们知道一......
  • CF850F 题解
    题意传送门有一袋\(n\)个颜色球，第\(i\)个颜色的球有\(a_i\)个。当袋子里至少有两个不同颜色的球时，执行以下步骤:一个接一个的按照顺序随机取出两个的球，这些球......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99