Kabaleo Lite
题意：有n种菜，每种菜都有对应的数量，然后只能选从1开始的连续的菜给顾客，求可以支持顾客数的最大值，并且在最大顾客数量的前提下求出盈利的最大值，最大盈利值可能为负数。
思路：前缀和+高精度。这题我是没有看出会爆long long，然后疯狂交，疯狂wa。我们很容易发现，因为要从第一个开始选，那么数量最大肯定是第一种菜的数量，然后，重点就是求当前情况下的最大的盈利值。
首先，我们先求到前缀和以及每种菜的前面的最小的菜的数量。
代码如下：
a[0]=0;
b[0]=0;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
if(i>1) b[i]=min(b[i],b[i-1]);
//将b数组转化为存储的是i之前的数量最小的那盘菜的数量
}
int ans1=b[1];
ll ans2=0;
for(int i=1;i<=n;i++) a[i]=a[i]+a[i-1]; //将a数组转化为求前缀和然后，我们在来看如何求最大的利润；
int l=1,r=1;
//现在b数组表示的是i之前的最小数量，a表示的是前缀和
ll m=a[l]*b[l];
while(r<n+1){
while(r<n+1&&a[r]<=a[l]) r++;
if(r==n+1) break;
m+=b[r]*(a[r]-a[l]);
ans2+=m/mod,m%=mod;
l=r;
}由于可能会爆long long，然后我们尽量避免将大的数进行直接相乘，我们分成一小步一小步来累加，我们先将l，r都初始化为起始点，然后，我们让r往右边找前缀和大于当前的l的那个位置，如果没有找到，说明我们已经求到了最优的利润了，直接退出，否则， m+=b[r]*(a[r]-a[l]);表示的是我们这段区间内对利润最大值还是有贡献的，（注意我们的a，b数组此时代表的值），其实思想就是将整个区间分成一小块一小块，然后对每块进行单独处理。接下来的ans2+=m/mod,m%=mod，（这里我们的mod=1e15,其中ans2表示的是商，m表示的mod之后的余数，其实这就是一个很好的高精度模拟方法，到时候只要输出ans2，再将m以15位进行输出即可。
代码如下：
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1e15;
ll a[100010];
ll b[100010];
int main(){
int t;
scanf("%d",&t);
for(int j=1;j<=t;j++){
a[0]=0;
b[0]=0;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
if(i>1) b[i]=min(b[i],b[i-1]);
}
int ans1=b[1];
ll ans2=0;
for(int i=1;i<=n;i++) a[i]=a[i]+a[i-1];
// for(int i=1;i<=n;i++) cout<<a[i]<<" ";
int l=1,r=1;
//现在b数组表示的是i之前的最小数量，a表示的是前缀和
ll m=a[l]*b[l];
while(r<n+1){
while(r<n+1&&a[r]<=a[l]) r++;
if(r==n+1) break;
m+=b[r]*(a[r]-a[l]);
ans2+=m/mod,m%=mod;
l=r;
}
printf("Case #%d: %d ",j,ans1);
if(ans2) printf("%lld%015lld\n",ans2,m);
else printf("%lld\n",m);
}
return 0;
}Interesting Computer Game
题意：有n个回合，每个回合给两个数字，然后选其中一个数字，问最后所得到的不同的数字个数最大为多少？
思路：图+并查集。对于题目的意思，我们可以转化为并查集进行处理，我们发现，可以将每个回合给出的a，b当作一条边的两个端点，最后构成图之后，我们选择n次，我们每次只能选择一个顶点，最后最多可以选择几个顶点。我们可以发现如下规律；
1、如果转化成图之后有的地方形成了环的话，从环出发可以到达的任意点都可以被选到，这个可以自己在纸上画图模拟看看。
2、对于没有构成环的部分，加入这个联通分量有n个点的话，我们就可以选择n-1个点，这个还是自己纸上模拟一下即可。
那么，接下来就说说怎么实现我们的想法了。
首先，我们知道a，b数值太大了，所以我们需要先用map进行离散化,关于离散化的知识建议自行百度。大体就是将一些无规律又很大的数字放到一个数组里面进行存储。
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
if(!mp[a[i]]) mp[a[i]]=num++;
if(!mp[b[i]]) mp[b[i]]=num++;
}我们将a，b依次放入mp容器里面（因为数组存不了这么大的数组），然后形成一一映射。
然后，我们还需要对初始化我们每个下标对应的父结点。
最核心的代码就是下面这个循环了：
int x,y;
for(int i=1;i<=n;i++){
x=findfather(mp[a[i]]),y=findfather(mp[b[i]]);
if(x!=y){
f[x]=y;
if(vis[x]||vis[y]) vis[y]=1,vis[x]=1;
}
else vis[y]=1;
}我们先对每次输入的a，b找到各自的父结点来，然后如果两者的父结点是一样的话，那么就说明可以形成环，我们把与环相连通的结点的下标都用vis数组标记为1，如果两者的父结点不一样的话，那么我们就把这两个父结点合并成一个父结点，但是如果这两个父结点中至少有一个被标记为可以与环相连通的话，那么我们就将两者的vis都标记为1.
最后，我们只要检查那些结点的下标没被标记，而且它的父结点还是自己本身的点，减去它们的个数即可。（其实这里是对那些没形成环，又不能与环相联通的那些点），也就是我们上面说到的第二种情况，肯定是有一个点不能被选到的，所以我们让父结点不被选到即可。
ac代码：
#include<iostream>
#include<map>
using namespace std;
map<int,int> mp;
int a[100010],b[100010];
bool vis[200010];
int f[200010];
int findfather(int x){
if(x!=f[x]) f[x]=findfather(f[x]);
return f[x];
}
int main(){
int T;
scanf("%d",&T);
for(int index=1;index<=T;index++){
int num=1;
mp.clear();
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
if(!mp[a[i]]) mp[a[i]]=num++;
if(!mp[b[i]]) mp[b[i]]=num++;
}
for(int i=1;i<num;i++) f[i]=i,vis[i]=0;
int x,y;
for(int i=1;i<=n;i++){
x=findfather(mp[a[i]]),y=findfather(mp[b[i]]);
if(x!=y){
f[x]=y;
if(vis[x]||vis[y]) vis[y]=1,vis[x]=1;
}
else vis[y]=1;
}
int ans=num-1;
for(int i=1;i<num;i++){
if(f[i]==i&&vis[i]==0) ans--;
}
printf("Case #%d: %d\n",index,ans);
}
return 0;
}Game SET
题意：其实题目的意思很好懂，每张牌有4个属性，然后就是从n张牌中选择出3张牌，对于这三张牌，不允许出现两张牌表示的是某个属性的同一个值，另一张牌表示的是该属性的不同的值，另外还有万能替换牌，可以替换成任意想要的那种类型的牌。
思路：模拟+暴力。其实这个题目是不难的，我到现在都觉得榜被带偏了。出题人给的那个证明的网页登不了，没办法，本人又比较菜，只能按出题的说的去做了。直接暴力。我们发现，每张牌都有4个属性，这很显然可以用结构体去进行存储，我们首要的任务是将每张牌的四个属性从输入中提取出来。
for(int i=1;i<=n;i++){
string ss;
cin>>ss;
// int len=ss.size();
int id=0;
for(int j=0;j<4;j++){
string fea;
if(ss[id]=='[') id++;
while(ss[id]!=']'){
fea+=ss[id];
id++;
}
if(ss[id]==']') id++;
card[i].feature[j]=fea;
}
}在确保输入是合法的前提下我们可以像上面那样提取出每张牌的4个属性。
题目之后，我们直接用3重循环来进行枚举，符合直接输出。对于judge函数，我们单独考虑每种属性，然后对于每种属性，我们可以单独记录下当前属性下的万能替换的次数，然后将其余每种属性统一放到set容器里面，我们发现，不能组成set的情况无非就是2+1，当然这里面是没有万能牌的，如果set容器里面的元素个数为2，并且万能牌没有的话，那么这种的肯定是不符合的，否则肯定是可以组成set的。
ac代码：
#include<iostream>
#include<string>
#include<set>
using namespace std;
struct Card{
string feature[4];
}card[300];
int icase=0;
int n;
bool judge(int x,int y,int z){
for(int i=0;i<4;i++){
set<string> st;
int mild_num=0;
if(card[x].feature[i]=="*") mild_num++;
else st.insert(card[x].feature[i]);
if(card[y].feature[i]=="*") mild_num++;
else st.insert(card[y].feature[i]);
if(card[z].feature[i]=="*") mild_num++;
else st.insert(card[z].feature[i]);
if(st.size()==2&&mild_num==0) return false;
}
return true;
}
void solve(){
for(int i=1;i<=n;i++){
string ss;
cin>>ss;
// int len=ss.size();
int id=0;
for(int j=0;j<4;j++){
string fea;
if(ss[id]=='[') id++;
while(ss[id]!=']'){
fea+=ss[id];
id++;
}
if(ss[id]==']') id++;
card[i].feature[j]=fea;
}
}
/*for(int i=1;i<=n;i++){
for(int j=0;j<4;j++) cout<<card[i].feature[j]<<" ";
cout<<endl;
}*/
bool k=false;
for(int i=1;i<=min(21,n);i++){
for(int j=i+1;j<=min(21,n);j++) {
for(int k=j+1;k<=min(21,n);k++){
if(judge(i,j,k)){
printf("Case #%d: %d %d %d\n",icase,i,j,k);
return;
}
}
}
}
printf("Case #%d: -1\n",icase);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
icase++;
scanf("%d",&n);
solve();
}
return 0;
}
京公网安备 11010502036488号