2020 CCPC河南省赛

A - 班委竞选

签到不多说

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<pair<int,int>>v[N];


bool cmp(pair<int,int>a,pair<int,int>b){
    if(a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,m; cin>>n>>m;
    set<int>s;
    for(int i = 1;i <= n; i++)
    {
        int c,t;
        cin>>c>>t;
        s.insert(c);
        v[c].push_back({t,i});
    }

    for(auto i : s)
    {
        sort(v[i].begin(),v[i].end(),cmp);
        cout<<v[i][0].second<<" ";
    }
    return 0;
}

C - 我得重新集结部队

这个读懂题就很容易啦，是个小模拟。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n;

ll dist(ll x1,ll y1,ll x2,ll y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

bool f[N];


vector<array<ll,4>>c;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n;
    memset(f,true,sizeof(f));
    
    for(int i = 1;i <= n; i++)
    {
        int op; cin>>op;
        if(op == 1)
        {
            ll x,y,h; cin>>x>>y>>h;
            c.push_back({x,y,h,i});
        }else{
            ll x1,y1,atk,r; cin>>x1>>y1>>atk>>r;
            ll mindist = 1e18,idx = -1;

            for(int j = 0;j < c.size(); j++){
                if(f[c[j][3]] == false)continue;
                ll x2 = c[j][0],y2 = c[j][1];
                if(dist(x1,y1,x2,y2) < mindist){
                    idx = j;
                    mindist = dist(x1,y1,x2,y2);
                }
            }
            if(idx == -1)continue;

            ll x2 = c[idx][0],y2 = c[idx][1];
            ll h = c[idx][2],evt = c[idx][3];

            x1 = x2,y1 = y2;
            for(int j = 0;j < c.size(); j++){
                if(f[c[j][3]] == false)continue;
                ll x2 = c[j][0],y2 = c[j][1];
                ll h = c[j][2],evt = c[j][3];
                ll d = dist(x1,y1,x2,y2);
                if(d <= r*r){
                    h -= 3 * atk;
                    if(h > 0){
                        f[i] = false;
                        c[j][2] = h;
                    }
                    else f[evt] = false;
                }
            }
        }
        
        
    }

    for(int i = 1;i <= n; i++){
        if(f[i])
            cout<<"Yes\n";
        else cout<<"No\n";
    }
    


    return 0;
}

E - 发通知 (离散化 + 差分)

题意：学院一共有 n 位学生，用 1, 2, …, n 编号。每天，学院都会派遣辅导员给学生发送若干通知，以保证各项措施、活动消息得到落实。

现在，学院要求辅导员发送一条关于光盘行动的通知。对于通知信息，同学们的反应往往各不相同，辅导员预测出第 号学生收到通知后会产生 的愉悦度。此外，辅导员还观察到第 i 号学生会在时间段内实时查阅通知消息，能够收到这段时间内的所有通知；而其他时间将无法收到通知（愉悦度为 0）。

辅导员会选择在某一时刻发布一次通知消息，他希望在至少有 k 名同学收到通知的前提下，使得同学们的总体愉悦度最大。同学们的总体愉悦度是所有同学愉悦度的异或和。请聪明的你帮助辅导员计算最大的总体愉悦度。

思路：关于区间操作，很容易会想到差分和前缀和。但是我们发现和都很大呀，但是也没有关系，离散化一下就好了。

对于区间，我们在+=,-=。同样的 ^= , ^= 。

离散化也是常操，unique一下。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
ll a[N],b[N],w[N];
ll d[N*2],t[N*2];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,k; cin>>n>>k;
    vector<ll>v;
    for(int i = 1;i <= n; i++)
    {
        cin>>a[i]>>b[i]>>w[i];
        v.push_back(a[i]);
        v.push_back(b[i]+1);
    }

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()))-v.end();
    
    for(int i = 1 ; i <= n ; i ++)
    {
        int l = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        int r = lower_bound(v.begin(), v.end(), b[i] + 1ll) - v.begin() + 1;
        d[l] += 1ll, d[r] -= 1ll;
        t[l] ^= w[i], t[r] ^= w[i];
    }
    ll ans = -1;
    int len = v.size();
    for(int i = 1 ; i <= len; i ++)
    {
        d[i] += d[i - 1];
        t[i] ^= t[i - 1];
        if(d[i] >= k)
        ans = max(ans,t[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

当然你愿意用map也是可以的，但是常数比较大

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

map<int,pair<int,int>>mp;

int main(){
	ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
	int n,k; cin>>n>>k;
	for(int i = 1;i <= n; i++)
	{
		int a,b,w; cin>>a>>b>>w;
			
		mp[a].first ^= w;
		mp[a].second += 1;

		mp[b+1].first ^= w;
		mp[b+1].second -= 1;
	}	

	
	int hav = 0;
	int ans = -1,now = 0;

	for(auto x : mp){
		now ^= x.second.first;
		hav += x.second.second;
		if(hav >= k)
			ans = max(ans,now);
	}

	cout<<ans<<"\n";
	return 0;
}

ps:布吉岛为什么，那么容易的我写了辣么久emmm，果然是太久没写啦。