Codeforces Round #751 (Div. 2)

Codeforces Round #751 (Div. 2)

A. Two Subsequences

找一个字典序最小的字母并输出，再输出去掉第一个最小字母的原字符串即可，代码略。

B. Divine Array

给我们一个数组，不停变换，将数字变换为其在数组中出现的次数，题问第k次变换后第x位的数是什么。

简单枚举可知，数组会经过一定次数的变换后稳定，不会再改变，直接存储输出即可。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef pair PUU;
#define RUSH cin.tie(),cout.tie(),ios::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define pai acos(-1.0)
inline ll qmi(ll a,ll b,ll mod){
	ll ans=1%mod;
	while(b){
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans%mod;
}
inline ll inv(ll a,ll mod){
	return qmi(a,mod-2,mod);
}
const int N=2010;
int a[N][N];
map las;
int main(){
	int _;
	cin>>_;
	while(_--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[0][i];
		for(int i=1;i<=n;i++){
			las.clear();
			for(int j=1;j<=n;j++) las[a[i-1][j]]++;
			for(int j=1;j<=n;j++) a[i][j]=las[a[i-1][j]];
		}
		int q,pos,k;
		cin>>q;
		while(q--){
			cin>>pos>>k;
			cout<

C. Array Elimination

给我们一个数组，让我们随意选其中k个数，使这k个数减去他们的异或和，最后使得数组元素都变为0，找出这些数k。

考虑拆分每个数的每一位，只需要每一位上1的个数都能被数k整除即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef pair PUU;
#define RUSH cin.tie(), cout.tie(), ios::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define pai acos(-1.0)
inline ll qmi(ll a, ll b, ll mod)
{
    ll ans = 1 % mod;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans % mod;
}
inline ll inv(ll a, ll mod)
{
    return qmi(a, mod - 2, mod);
}
const int N = 200010;
int a[N][25];
int ans[N];
int cnt[35];
int main()
{
    int _;
    cin >> _;
    while (_--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            for (int j = 0; j < 30; j++)
                if ((x >> j) & 1)
                    cnt[j]++;
        }
        for (int i = 1; i <= n; i++)
        {
            bool flag = true;
            for (int j = 0; j < 30; j++)
            {
                if (cnt[j] % i != 0)
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
                cout << i << ' ';
        }
        for (int i = 0; i < 30; i++)
            cnt[i] = 0;
        cout << endl;
    }
    return 0;
}

D. Frog Traveler

一只青蛙在井底，在距离地面x米的地方可以往上跳[0,a[x]]米，设跳完之后离地面有y米，在下一次起跳之前会掉落b[y]米，问我们跳的最少次数以及路径。

直接bfs即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef pair PUU;
#define RUSH cin.tie(), cout.tie(), ios::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define pai acos(-1.0)
inline ll qmi(ll a, ll b, ll mod)
{
    ll ans = 1 % mod;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans % mod;
}
inline ll inv(ll a, ll mod)
{
    return qmi(a, mod - 2, mod);
}
//hha
const int N = 300010;
int a[N], b[N];
bool st[N];
int f[N];
int fr[N];
int n;

void out_pp(int x)
{
    if (x >= n)
        return;
    out_pp(fr[x]);
    cout << x << ' ';
}
bool bfs()
{
    queue q;
    memset(st, 0, sizeof(st));
    memset(f, 0x3f, sizeof(f));
    st[n] = 1;
    q.push(n);
    f[n] = 0;
    int dis = n;
    while (q.size())
    {
        auto t = q.front(); // LAS DEPTH
        q.pop();
        int now = t + b[t]; // NOW DEPTH
        // 可以跳 1~a[now] 最大跳到 now+a[now]
        for (int to = min(now, dis - 1); to >= now - a[now]; to--)
        {
            if (to <= 0)
            {
                to = 0;
                f[to] = f[t] + 1;
                fr[to] = t;
                cout << f[to] << endl;
                out_pp(0);
                return true;
            }
            f[to] = f[t] + 1;
            fr[to] = t;
            q.push(to);
        }
        dis = min(dis, now - a[now]);
    }
    return false;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int j = 1; j <= n; j++)
        cin >> b[j];
    if (bfs())
        return 0;
    else
        return puts("-1") * 0;
}

E. Optimal Insertion

给一个长度为n的数组a和长度为m的数组b，让我们把数组b插入到a中，并且使得所产生的新的数组的逆序对个数最少。

如果要使得所产生的逆序对个数最少，那么b必定是在自身排序后再有序插入到a中，（小的在前面，大的在后面）防止与原数组自身产生新的逆序对。

这样只需要分治找到b中每一个数需要插入的位置即可，造出新数组之后用树状数组（或者归并排序）求逆序对即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef pair PUU;
#define RUSH cin.tie(), cout.tie(), ios::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define pai acos(-1.0)
inline ll qmi(ll a, ll b, ll mod)
{
    ll ans = 1 % mod;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans % mod;
}
inline ll inv(ll a, ll mod)
{
    return qmi(a, mod - 2, mod);
}
const int N = 2020100;
int a[N], b[N], pos[N];
int tr[N];
int c[N];
int d[N];
int n, m;
int prpr = 0;
inline int lowbit(int x)
{
    return x & -x;
}
inline void add(int x)
{
    for (int i = x; i <= prpr; i += lowbit(i))
        tr[i]++;
}

inline void dadd(int x)
{
    for (int i = x; i <= prpr; i += lowbit(i))
        tr[i]--;
}

inline ll sum(int x)
{
    ll res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
inline int find(int x)
{
    int l = 1, r = prpr;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (d[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}
void get_pos(int a[], int b[], int pos[], int l, int r, int L, int R)
{
    if (l > r)
        return;
    int mid = l + r >> 1;
    int loc = L, minv = 0, now = 0;
    for (int i = L + 1; i <= R; i++)
    {
        if (a[i - 1] > b[mid])
            now++;
        if (a[i - 1] < b[mid])
            now--;
        if (now < minv)
        {
            minv = now;
            loc = i;
        }
    }
    pos[mid] = loc;
    get_pos(a, b, pos, l, mid - 1, L, loc);
    get_pos(a, b, pos, mid + 1, r, loc, R);
}
int main()
{
    RUSH;
    int _;
    cin >> _;
    while (_--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= m; i++)
            cin >> b[i];
        sort(b + 1, b + 1 + m);
        get_pos(a, b, pos, 1, m, 1, n + 1);
        int cnt = 0, now = 0;
        for (int i = 1; i <= m; i++)
        {
            while (pos[i] - 1 > now)
                c[++cnt] = a[++now];
            c[++cnt] = b[i];
        }
        while (now < n)
            c[++cnt] = a[++now];
        for (int i = 1; i <= n + m; i++)
            d[i] = c[i];
        sort(d + 1, d + 1 + n + m);
        cnt = 1;
        for (int i = 2; i <= n + m; i++)
        {
            if (d[i] != d[cnt])
                d[++cnt] = d[i];
        }
        prpr = cnt;
        ll res = 0;
        for (int i = 1; i <= n + m; i++)
        {
            int x = find(c[i]);
            res += sum(prpr) - sum(x);
            add(x);
        }
        for (int i = 1; i <= n + m; i++)
        {
            int x = find(c[i]);
            dadd(x);
        }
        cout << res << endl;
    }
    return 0;
}

By 泽浩巨巨

ICPC

相关

ICPC2021（济南）打星队线上打铁游记

[ICPC] 2021济南E.Insidemen

2019ICPC南京网络赛B super_log

第十三届河南省ACM-ICPC游记

第46届ICPC亚洲区域赛(沈阳)L-Perfect Matchings【dp,组合数学】

2021 icpc 沈阳游记

2019 ICPC Asia-East Continent Final

2020 ICPC Shanghai Site

ICPC 2020 EC-Final 游记（上）

[ICPC2018西安I] Misunderstood … Missing - dp

[ICPC2020南京D] Degree of Spanning Tree - 树

[ICPC2020济南L] Bit Sequence - 数位dp

标签