G Game SET
链接：https://ac.nowcoder.com/acm/contest/5673/G
题意：
就是多组输入，每次输入给定n个字符串，每个字符串有四个属性，每个属性分别有三个选项，这三个选项用三个不同的字符串，或者用*来表示没有选项来表示，问是否存在三个字符串，他们四个属性各不相同，或者都一样。有的话输出编号，没有输出-1.
题解：先分别将这四种属性的选项用map容器赋值，简化，再O(n^3)进行遍历三个三个进行比较，看他们四个属性是否都不相同，或者都一样
注意：
*与 *之间他们的也算不同，因为表示null，所以不能算属性相同。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
//const ll mod=998244353;
map<string,int>m;
char str[105];
void init()
{
m["one"]=1;
m["two"]=2;
m["three"]=3;
m["diamond"]=1;
m["squiggle"]=2;
m["oval"]=3;
m["solid"]=1;
m["striped"]=2;
m["open"]=3;
m["red"]=1;
m["green"]=2;
m["purple"]=3;
m["*"]=0;
}
struct node{int c[5];}trans[300];
bool check(int x,int y,int z)
{
for(int i=1;i<=4;i++)
{
set<int>st;
int wild=0;
if(trans[x].c[i]==0)wild++;
else st.insert(trans[x].c[i]);
if(trans[y].c[i]==0)wild++;
else st.insert(trans[y].c[i]);
if(trans[z].c[i]==0)wild++;
else st.insert(trans[z].c[i]);
if(st.size()>1&&st.size()+wild<3)return false;
}
return true;
}
int main()
{
int t,n;
scanf("%d",&t);
init();
int cas=0;
while(t--)
{ cas++;
scanf("%d",&n);
int i,j,k;
for( i=1;i<=n;i++)
{
scanf("%s",str);
k=1;
for(j=1;j<=4;j++)
{
string a;
for(k;str[k]!=']';k++)
{
a+=str[k];
}
trans[i].c[j]=m[a];
k+=2;
}
}
int flag=0;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
for(k=j+1;k<=n;k++)
{
if(check(i,j,k))
{
flag=1;break;
}
}
if(flag)break;
}
if(flag)break;
}
if(!flag)printf("Case #%d: -1\n",cas);
else printf("Case #%d: %d %d %d\n",cas,i,j,k);
}
return 0;
}I Interesting Computer Game
链接：https://ac.nowcoder.com/acm/contest/5673/I
题意：
给出n对数字 a,b。在每一对数中选择一个与之前的不同的数，若没有则不选，求最多能选出多少数
题解：
先离散化一下，构建一个并查集，找出每个根节点能够联通的最多的个数，稍微根据题意修改一下
注意：
若没有出现成环的情况，则需要-1，因为最开始的根节点和它的一个子节点需要二选一
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
//const ll mod=998244353;
int a[maxn],b[maxn],fa[maxn],cnt[maxn],vis[maxn],val[maxn],ans,n,k,T;
int get(int x)
{
if(fa[x]!=x)fa[x]=get(fa[x]);
return fa[x];
}//得到x的根节点
void combine(int u,int v)//先把两个点给连接起来成为一条边
{
int temp1=get(u);
int temp2=get(v);//
if(temp1==temp2){vis[temp1]=1;}//说明这是一个环
else
{
if(vis[temp1]||vis[temp2]){vis[temp1]=vis[temp2]=1;}//
cnt[temp1]+=cnt[temp2];//求出每个节点所包含的节点（包括自己）
fa[temp2]=temp1;//合并，v是u的父节点。
}//
}
void init(int t)
{
for(int i=1;i<=t;i++)
{
fa[i]=i;
cnt[i]=1;
vis[i]=0;//表示是否有成环
}
k=1;ans=0;
}//初始化
int main()
{
scanf("%d",&T);
int cas=0;
while(T--)
{
cas++;
scanf("%d",&n);
init(n*2);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
val[k++]=a[i];
val[k++]=b[i];//把所有的数放入一个大的数组里面去
}
sort(val+1,val+k);
int t= unique(val+1,val+k)-val-1;//表示一共有多少个不重复的数字,此时的val已经是去重后的函数
//printf("%d",t);
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(val+1,val+t,a[i])-val;//表示原先这个数在去重，排大小数列数列中的位置
b[i]=lower_bound(val+1,val+t,b[i])-val;
//printf("%d %d\n",a[i],b[i]);
}//离散化，O（n)//a[i],b[i]就只能是1~t里面的数了
for(int i=1;i<=n;i++)
{
combine(a[i],b[i]);//连接a[i],b[i]的编号。
}
for(int i=1;i<=t;i++)
{
if(get(i)==i)//根节点（找到根节点）
{
ans+=cnt[i]+vis[i]-1;//表示是否成环，若没有成环就要减去初始的一个（根节点直接加进去了）
}
}
printf("Case #%d: %d\n",cas,ans);
//for(int i=1;i<=t;i++)printf("%d ",val[i]);
//for(int i=1;i<=t;i++)printf("%d ",get(i));
}
return 0;
}K Kabaleo Lite
链接：https://ac.nowcoder.com/acm/contest/5673/K
题意：
就是说有n盘菜，第i个菜有a[i]个价值，和个数b[i]，然后要求一堆人必须连续的吃，求吃得到的最大的价值
题解：
其实就是求前缀和问题，人数从b[1]开始慢慢减少，然后只要连续的前缀和大于0就进行叠加
注意：
它还卡了快读，最后的和大于ll范围，需要用到__int128，但是windows系统上clion好像又对这个玩意报错，玄学。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
const int inf=0x3f3f3f3f;
//const ll mod=998244353;
ll a[maxn],b[maxn],s[maxn];
inline __int128 read(){ //__int128 可以换成 int longlong 基于自己的需求即可，板子
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void out(__int128 x){ //输出
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
out(x/10);
putchar(x%10+'0');
}
int main()
{
int t,n,l,r;__int128 ans;
t=read();
int cas=0;
while(t--)
{
cas++;
n=read();s[0]=0;b[0]=inf;a[0]=0;
for(int i=1;i<=n;i++)
{
a[i]=read();
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
b[i]=read();
b[i]=min(b[i],b[i-1]);//找到当前最小的限制人数
}
ans=a[1]*b[1];
r=l=1;
while(r<=n)
{
while(s[r]<=s[l]&&r<=n)r++;//分块
if(r==n+1)break;//全是小于s[1]
ans+=b[r]*(s[r]-s[l]);
l=r;
}
printf("Case #%d: %lld ",cas,b[1]);
out(ans);
printf("\n");
}
return 0;
}
京公网安备 11010502036488号