比赛地址
Pro: 3/3/11
Rank: 55/685
[G] Game SET
题意
给出一些扑克牌,牌面上有四个属性,每种属性有三种可能的取值,还可能是通配符.问能否选出三张牌,使得它们每个属性都互不相同或者完全一样.
题解
直接暴力枚举后两张牌是什么,枚举过的牌按照所有可能的贡献加到一个集合里,之后枚举的时候就可以O(1)检测了.
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define IL inline
#define reg register
#define N 266
using namespace std;
int T,n,i;
char c[N];
int v[5][5][5][5];
struct Data{
int f[5];
}a[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Work(int x){
reg int i=0,len=strlen(c),s=0;
for (i=0;i<len;i++){
if (c[i]=='['){
s++; i++;
if (c[i]=='*') a[x].f[s]=0;
else {
if (s==1){
i++;
if (c[i]=='n') a[x].f[s]=1;
if (c[i]=='w') a[x].f[s]=2;
if (c[i]=='h') a[x].f[s]=3;
} else if (s==2){
if (c[i]=='d') a[x].f[s]=1;
if (c[i]=='s') a[x].f[s]=2;
if (c[i]=='o') a[x].f[s]=3;
} else if (s==3){
i++;
if (c[i]=='o') a[x].f[s]=1;
if (c[i]=='t') a[x].f[s]=2;
if (c[i]=='p') a[x].f[s]=3;
} else {
if (c[i]=='r') a[x].f[s]=1;
if (c[i]=='g') a[x].f[s]=2;
if (c[i]=='p') a[x].f[s]=3;
}
}
}
}
// cout<<a[x].f[1]<<" "<<a[x].f[2]<<" "<<a[x].f[3]<<" "<<a[x].f[4]<<endl;
}
IL void Insert(int x){
reg int i=0,j=0,k=0,g=0;
for (i=0;i<=3;i++){
if (i && a[x].f[1] && i!=a[x].f[1]) continue;
for (j=0;j<=3;j++){
if (j && a[x].f[2] && j!=a[x].f[2]) continue;
for (k=0;k<=3;k++){
if (k && a[x].f[3] && k!=a[x].f[3]) continue;
for (g=0;g<=3;g++){
if (g && a[x].f[4] && g!=a[x].f[4]) continue;
v[i][j][k][g]=x;
}
}
}
}
}
IL void Cal(){
reg int i=0,j=0,p=0,q=0,s=0,w=0;
memset(v,0,sizeof(v));
Insert(1);
for (i=2;i<=n;i++){
for (j=i+1;j<=n;j++){
if (!a[i].f[1] || !a[j].f[1]) p=0;
else if (a[i].f[1]==a[j].f[1]) p=a[i].f[1];
else p=a[i].f[1]^a[j].f[1];
if (!a[i].f[2] || !a[j].f[2]) q=0;
else if (a[i].f[2]==a[j].f[2]) q=a[i].f[2];
else q=a[i].f[2]^a[j].f[2];
if (!a[i].f[3] || !a[j].f[3]) s=0;
else if (a[i].f[3]==a[j].f[3]) s=a[i].f[3];
else s=a[i].f[3]^a[j].f[3];
if (!a[i].f[4] || !a[j].f[4]) w=0;
else if (a[i].f[4]==a[j].f[4]) w=a[i].f[4];
else w=a[i].f[4]^a[j].f[4];
if (v[p][q][s][w]){
//cout<<p<<" "<<q<<" "<<s<<" "<<w<<endl;
printf("%d %d %d\n",v[p][q][s][w],i,j);
goto END;
}
}
Insert(i);
}
puts("-1");
END:;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
for (int t=1;t<=T;t++){
printf("Case #%d: ",t);
n=read();
for (i=1;i<=n;i++){
scanf("%s",&c);
Work(i);
}
if (n<=2){
puts("-1");
continue;
}
Cal();
}
return 0;
}
[I] Interesting Computer Game
题意
有n轮游戏,每一轮会给出两个数字,每一次只能选择一个从没选过的数字,或者什么都不做.问最后最多选出几个数字.
题解
将同一轮出现的数字视为两个点与一条边,然后生成的图如果有环的话,环上所有的数字都能选上,否则会少选一个.DFS求一遍即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
int flag, a[100005], b[100005], used[200005];
int tot, fir[400005], nxt[400005], adj[400005], cnt, tab[400005];
map <int, int> M;
void add(int a, int b) {
adj[++tot] = b;
nxt[tot] = fir[a];
fir[a] = tot;
tab[tot] = cnt;
}
int dfs(int a, int from) {
used[a] = 1;
int ret = 1;
for (int t = fir[a]; t; t = nxt[t]) {
if (used[adj[t]]) {
if (tab[t] != from) flag = 1;
continue;
}
ret += dfs(adj[t], tab[t]);
}
return ret;
}
int main(){
int T; cin >> T; for (int TT = 1; TT <= T; TT++) {
int n; scanf("%d", &n);
int id = 0; M.clear();
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a[i], &b[i]);
if (!M[a[i]]) M[a[i]] = ++id;
if (!M[b[i]]) M[b[i]] = ++id;
}
for (int i = 1; i <= n; i++) { a[i] = M[a[i]]; b[i] = M[b[i]]; }
tot = cnt = 0;
for (int i = 1; i <= 200000; i++) used[i] = 0;
for (int i = 1; i <= 400000; i++) fir[i] = nxt[i] = adj[i] = 0;
for (int i = 1; i <= n; i++) { cnt++; add(a[i], b[i]); add(b[i], a[i]); }
int ans = 0;
for (int i = 1; i <= id; i++) if (used[i] == 0) {
flag = 0;
ans += dfs(i, 0) - 1;
ans += flag;
}
printf("Case #%d: %d\n", TT, ans);
}
return 0;
}
[K] Kabaleo Lite
题意&题解
签到题
中间计算结果会爆long long,需要用int128来储存.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
__int128_t a[100005], b[100005], val[100005], num[100005], ans;
long long int p;
inline void Write(__int128_t x) {
static int sta[22];
register int top=0;
if (x<0) {putchar('-'); x=-x;}
do{
sta[top++]=x%10,x/=10;
}while (x);
while (top) putchar(sta[--top]+48);
}
int main(){
int T; cin >> T; for (int TT = 1; TT <= T; TT++) {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) { scanf("%lld", &p); a[i] = p; a[i] += a[i-1]; }
for (int i = 1; i <= n; i++) { scanf("%lld", &p); b[i] = p; if (i > 1 && b[i] > b[i-1]) b[i] = b[i-1];}
for (int i = 0; i <= n+1; i++) val[i] = num[i] = 0;
int tot = 1; ans = 0;
val[1] = a[1]; num[1] = b[1];
for (int i = 2; i <= n; i++) {
if (a[i] > val[tot]) {
tot++;
val[tot] = a[i];
num[tot] = b[i];
}
}
for (int i = tot; i >= 1; i--) ans += val[i] * (num[i] - num[i+1]);
printf("Case #%d: ", TT);
Write(b[1]); printf(" "); Write(ans); printf("\n");
}
return 0;
}
总结
区分度不太友好的一场.主要暴露的问题是知识面有些狭窄.例如A题是一个离线的动态图连通性问题,可以用线段树+可撤销并查集解决,算是一个比较裸的题目,但是比赛中因为不知道这个手法一度认为不可做.之后看来要着重补一下考察频率较高的知识点.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020牛客暑期多校第八场
本文地址: 2020牛客暑期多校第八场
