2020牛客暑期多校训练营（第八场）

比赛链接

G Game SET

出题人表示直接暴力就好……

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 505;

int n;
string s;
int p[N][10];

inline bool check(int i, int j, int k){
	for(int l = 1; l <= 4; l++){
		if(p[i][l] && p[j][l] && p[k][l]){
			if(p[i][l] != p[j][l] && (p[i][l] == p[k][l] || p[j][l] == p[k][l]))	return false;
			if(p[j][l] != p[k][l] && (p[j][l] == p[i][l] || p[k][l] == p[i][l]))	return false;
			if(p[k][l] != p[i][l] && (p[k][l] == p[j][l] || p[i][l] == p[j][l]))	return false;
		}
	}
	return true;
}

inline void solve(int T){
	if(n <= 2){ printf("Case #%d: -1\n", T); return; }
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			for(int k = j + 1; k <= n; k++){
				if(check(i, j, k)){
					printf("Case #%d: %d %d %d\n", T, i, j, k);
					return;
				}
			}
		}
	}
	printf("Case #%d: -1\n", T);
}

inline int f(string t){
	if(t == "one")		return 1;
	if(t == "two")		return 2;
	if(t == "three")	return 3;
	if(t == "diamond")	return 1;
	if(t == "oval")		return 2;
	if(t == "squiggle")	return 3;
	if(t == "solid")	return 1;
	if(t == "striped")	return 2;
	if(t == "open")		return 3;
	if(t == "red")		return 1;
	if(t == "green")	return 2;
	if(t == "purple")	return 3;
	if(t == "*")		return 0;
}

int main(){
	int CASES = 0;
	int T; for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++){
			cin >> s;
			string t;
			int cnt = 0;
			for(int j = 0; j < s.size(); j++){
				if(s[j] == '[')	t.clear();
				else if(s[j] == ']')	p[i][++cnt] = f(t);
				else	t += s[j];
			}
		}
		solve(++CASES);
	}
	return 0;
}

---

I Interesting Computer Game

把每个数字看成点，一对数看成边，则形成一个含若干连通分量的图。若一个连通分量中含有环，则其大小加入答案；否则，其大小减一加入答案。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, a[N], b[N], t[N];

int fa[N], sz[N];
bool loop[N];
int findfa(int x){ return x == fa[x] ? x : fa[x] = findfa(fa[x]); }
void unionn(int x, int y){
	x = findfa(x), y = findfa(y);
	fa[y] = x;
	loop[x] |= loop[y];
	sz[x] += sz[y];
}

int main(){
	int CASES = 0;
	int T; for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= (n << 1); i++)
			fa[i] = i, loop[i] = false, sz[i] = 1;
		t[0] = 0;
		for(int i = 1; i <= n; i++){
			read(a[i], b[i]);
			t[++t[0]] = a[i], t[++t[0]] = b[i];
		}
		sort(t+1, t+t[0]+1);
		t[0] = unique(t+1, t+t[0]+1) - (t+1);
		for(int i = 1; i <= n; i++){
			a[i] = lower_bound(t+1, t+t[0]+1, a[i]) - t;
			b[i] = lower_bound(t+1, t+t[0]+1, b[i]) - t;
			if(findfa(a[i]) == findfa(b[i]))	loop[findfa(a[i])] = true;
			else	unionn(a[i], b[i]);
		}
		int ans = 0;
		for(int i = 1; i <= t[0]; i++){
			if(fa[i] != i)	continue;
			ans += loop[i] ? sz[i] : sz[i] - 1;
		}
		printf("Case #%d: %d\n", ++CASES, ans);
	}
	return 0;
}

---

K Kabaleo Lite

先把 $b$ 削成不增的，然后在前缀和最大处取完，如此不断进行即可。

这道题居然丧心病狂地卡 long long，要用 __int128……

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int n;
LL a[N], b[N];

void print(__int128 x){
	if(!x)	return;
	if(x < 0)	putchar('-'), x = -x;
	print(x / 10);
	putchar(x % 10 + '0');
}

int main(){
	int CASES = 0;
	int T; for(read(T); T; T--){
		read(n);
		b[0] = 1e5;
		priority_queue< pair<LL, int> > q;
		for(int i = 1; i <= n; i++){
			read(a[i]), a[i] += a[i-1];
			q.push(mp(a[i], i));
		}
		for(int i = 1; i <= n; i++)
			read(b[i]), b[i] = min(b[i-1], b[i]);
		int pt = n;
		__int128 ans = 0;
		LL val = 0, cnt = 0;
		while(1){
			while(!q.empty() && (q.top().second > pt || b[q.top().second] <= cnt))	q.pop();
			if(q.empty())	break;
			pt = q.top().second, val = q.top().first; q.pop();
			ans += (__int128)val * (b[pt] - cnt);
			cnt = b[pt];
		}
		printf("Case #%d: %lld ", ++CASES, cnt), print(ans), puts("");
	}
	return 0;
}