2022.07.10 summer training personal qualifying (V)

2022.07.10 Summer training Individual qualifying （ 5、 ... and ）

Post game introspection

Bottom of the line . Two thinking problems are always at odds with your own wrong ideas , I'm not sober enough when doing questions . The back state collapsed directly .

Problem B

Source

HDU-5145

Answer key

No, Mo team was directly stuck .

Mo team + Combinatorial mathematics . Each time a point is added, it means to divide by the factorial of the number of occurrences of this number . Record every time you add or delete .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int mod = 1e9 + 7;
const int N = 3e4 + 5;
int n, T = 1, m;
int a[N];
int cnt[N];
int power[N];
int len;
struct BBB {
    
    int l, r, id, flag;
    int ans;
}b[N];

void ready()
{
    
    power[0] = 1;
    ffor(i, 1, 30000) {
    
        power[i] = (ll)power[i - 1] * i % mod;
    }
}

int t = 1;

int get_(int x) {
    
    return x / len;
}

bool cmp(BBB i, BBB j) {
    
    if (i.flag == j.flag) return i.r < j.r;
    return i.flag < j.flag;
}

bool cmpid(BBB i, BBB j) {
    
    return i.id < j.id;
}

int qsm(int x, int y) {
    
    int res = 1;
    while (y) {
    
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

void add(int x, int& res) {
    
    if (!cnt[x]) res++;
    cnt[x]++;
    t = t * cnt[x] % mod;
}

void del(int x, int& res) {
    
    t = t * qsm(cnt[x], mod - 2) % mod;
    cnt[x]--;
    if (!cnt[x]) res--;
}


void work()
{
    
    cin >> n >> m;
    len = sqrt(n);
    ffor(i, 1, n)
        cin >> a[i];
    t = 1;
    ffor(i, 1, m) {
    
        cin >> b[i].l >> b[i].r;
        b[i].id = i;
        b[i].flag = get_(b[i].l);
    }
    mst(cnt, 0);
    sort(b + 1, b + m + 1, cmp);
    for (int k = 1, i = 0, j = 1, res = 0; k <= m; k++) {
    
        int id = b[k].id, l = b[k].l, r = b[k].r;
        while (i < r) add(a[++i], res);
        while (i > r) del(a[i--], res);
        while (j < l) del(a[j++], res);
        while (j > l) add(a[--j], res);
        b[k].ans = power[r - l + 1] * qsm(t, mod - 2) % mod;
    }
    sort(b + 1, b + m + 1, cmpid);
    ffor(i, 1, m) cout << b[i].ans << '\n';
}


signed main()
{
    
    IOS;
    ready();
    cin >> T;
    while (T--) {
    
        work();
    }
    return 0;
}

Problem E

Source

Codeforces-1301C

Answer key

Thinking structure problem . take 0 The number of is equally divided in m+1 Only one interval is required , That is, every one of them 1 Between （ Including both sides ） Try to have an equal number of 0. In this way, we can guarantee what we can contribute 0 The value contributed is the most .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;



int n, T = 1;

void ready()
{
    

}

int get_(int x) {
    
	return x * (x + 1) / 2;
}

void work()
{
    
	int m;
	cin >> n >> m;
	n = n - m;
	int c1 = n % (m + 1);
	int c2 = m + 1 - c1;
	int n1 = n / (m + 1) + 1;
	int n2 = n / (m + 1);
	int ans = get_(n + m) - c1 * get_(n1) - c2 * get_(n2);
	cout << ans << '\n';
}

signed main()
{
    
	IOS;
		cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem F

Source

Codeforces-1304C

Answer key

Record the current achievable range each time . If there is no intersection between the next guest's interval and the current interval , That is, unsatisfied .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int N = 105;
int n, T = 1;
struct FFF {
    
    int t, l, r;
}a[N];
void ready()
{
    

}

bool cmp(FFF i, FFF j) {
    
    if (i.t == j.t) {
    
        return (i.r - i.l + 1) > (j.r - j.l + 1);
    }
    return i.t < j.t;
}

bool work()
{
    
    int nx, ny;
    cin >> n >> nx;
    ny = nx;
    ffor(i, 1, n) cin >> a[i].t >> a[i].l >> a[i].r;
    // cout<<'\n';
    a[0].t = 0;
    //sort(a + 1, a + n + 1, cmp);
    ffor(i, 1, n) {
    
        int d = a[i].t - a[i - 1].t;
        int lx = nx - d, ly = ny;
        int rx = nx, ry = ny + d;
        int x = lx, y = ry;
        // cout<<nx<<' '<<ny<<'\n';
        // cout<<x<<' '<<y<<'\n'<<'\n';
        if (y < a[i].l || a[i].r < x) return false;
        //nx = max(x, a[i].l);
        //ny = min(y, a[i].r);
        //cout << x << ' ' << y << '\n';
        if (a[i].l <= x && y <= a[i].r) {
    
            nx = x; ny = y;
            continue;
        }
        if (x <= a[i].l && a[i].r <= y) {
    
            nx = a[i].l; ny = a[i].r;
            continue;
        }
        if (y >= a[i].l && y<a[i].r) {
    
            nx = a[i].l; ny = y;
            continue;
        }
        if (a[i].r >= x) {
    
            nx = x; ny = a[i].r;
            continue;
        }
    }
    return true;
}

signed main()
{
    
    IOS;
    ready();
    cin >> T;
    while (T--) {
    
        if (work()) cout << "YES\n";
        else cout << "NO\n";

    }
    return 0;
}






/* 2 -7 15 -5 4 20 1 8 */

Problem G

Source

Codeforces-1301A

Answer key

At the same position ,c Must be with a or b At least one is the same , Then you can finish .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int N=105;
int n, T = 1;
string a,b,c;


void ready()
{
    

}


bool work()
{
    
    cin>>a>>b>>c;
    int len=a.size();
    ffor(i,0,len-1){
    
        if(c[i]!=a[i] && c[i]!=b[i])
            return false;
    }
    return true;
}

signed main()
{
    
	IOS;
    ready();
	cin>>T;
	while (T--) {
    
		if(work()) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}