emmm,于是我又来水文章了（
（传送门）
A. Yellow Cards (CF1215A)
题意
给定黄牌的数量，判断被踢下场人数的最大值和最小值
题解
算是个贪心？算最小值时就先把每个人最大的数量减一减去，还剩几个黄牌就最少走几个人。算最大时先把需要黄牌少的人先踢光再去看能踢几个需要黄牌多的队的人。。。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int a1,a2,k1,k2,n;
while (scanf("%d%d%d%d%d",&a1,&a2,&k1,&k2,&n) != EOF){
//min
int nu = a1*(k1-1)+a2*(k2-1);
int cardleft = n-nu;
if(cardleft<0)cardleft=0;
//max
int out1,out2;
if(k1>k2){
out2 = n / k2;
n -= out2 * k2;
if(out2 > a2){
n += (out2-a2)*k2;
out2 = a2;
}
out1 = n / k1;
}
else{
out1 = n / k1;
n -= out1 * k1;
if(out1 > a1){
n += (out1-a1)*k1;
out1 = a1;
}
out2 = n / k2;
}
//out
printf("%d %d\n",cardleft,out1+out2);
}
return 0;
}（感觉还可以再优化下的，懒得改了，之后再说吧emm
B.The Number of Products (CF1215B)
题意
给定一个不为零的数字序列，求连续的相乘为正数和复数的子序列各有多少给。
题解
（刚开始写的暴力，结果超时了QAQ。之后看落叶dalao后写的）
差不多就是遍历一遍数组，记下以当前元素为结尾的子序列相乘得正数和负数的各有多少，再读一个数，如果是正数就在得正数的子序列数量加一，如果是负数就在得正数的子序列数量加一再交换一下得正负的子序列的数量（自己在草稿纸上瞎算总结出来的）再之后在总的得正负的子序列数量加上本轮的以最后一个元素结尾相乘得正负的子序列的数量就行了（我都不知道自己在说些什么）。。还是看代码吧。。
代码
#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 200005
#define int ll
using namespace std;
int num[Max],f[Max][2];
//0 for positive, 1 for negative.
il int read()
{
char c=getchar();
int x=0,f=1;
while(c>'9'||c<'0')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
signed main(){
int n = read();
int last_neg_seq = 0, last_pos_seq = 0;
int neg = 0, pos = 0;
for(int i = 0;i < n;i++){
int tmp = (int)(read()<0);
last_pos_seq++;
if(tmp){
int tmp2 = last_pos_seq;
last_pos_seq = last_neg_seq;
last_neg_seq = tmp2;
}
neg += last_neg_seq;
pos += last_pos_seq;
//debug;
//printf("%d %d %d %d\n",last_neg_seq,last_pos_seq,neg,pos);
}
//printf("%d %d",neg,pos);
cout<<neg<<" "<<pos;
return 0;
}C.Swap Letters (CF1215C)
题意
给定两个由a和b组成的字符串，每次可以调换一个上面的和一个下面的元素。求使两个字符串相同需要的最少调换次数和调换步骤。
题解
首先统计下a的数量，如果a为奇数个，那就不可能使上下相同，直接输出-1.读入数组时统计下上下不同的位置和上面的元素是a还是b。如果a和b都是偶数个就可以简单的直接一次拿两个a或两个b的index就先，如果a和b都是奇数个，第一次就拿一个a和一个b，先输出两遍a的index，接下来就当作第一种情况就行了233.
代码
#include <bits/stdc++.h>
using namespace std;
char str[2][200100] = { 0 };
int sa[200100],sb[200100];
int pa=0,pb=0,pa2=0,pb2=0;
int ans = 0;
int main(){
int n;
cin>>n;
int num = 0;
for(int i = 0;i < 2;i++){
scanf("%s",str[i]);
}
for(int i = 0;i < n;i++){
if(str[0][i] != str[1][i]){
num++;
str[0][i]=='a'?sa[pa++]=i:sb[pb++]=i;
}
}
//debug;
//printf("%s\n%s\n",str[0],str[1]);
if(num%2){printf("%d\n",-1);return 0;
}
else{
if(pa%2){
printf("%d\n",num/2+1);
printf("%d %d\n",sa[pa2]+1,sa[pa2]+1);
printf("%d %d\n",sa[pa2++]+1,sb[pb2++]+1);
}
else printf("%d\n",num/2);
while(pa2<pa){
printf("%d %d\n",sa[pa2++]+1,sa[pa2++]+1);
}
while(pb2<pb){
printf("%d %d\n",sb[pb2++]+1,sb[pb2++]+1);
}
}
}D. Ticket Game (CF1215D)
题意
有长度为n的串，内容为0-9数字或'?'。Mono先手，填数。Mono希望前n/2个数和!=后n/2个数和。Bicarp希望相等。问谁能赢。
题解
自己不会解QAQ，这里就转载下某大佬的解吧emm
博弈论 Codeforces1215D Ticket Game
分析：先是高级做法
设L为左半边减右半部最小情况（左边污染部分全赋为0，右边全赋为9），R为左半边减右半边最大情况
若（L+R）/2=0，则B赢，否则就是A赢。
证明：若没有污染部分，则显然（L+R）/2=0，就是B赢，否则就是A赢。
若有污染部分，第一个玩家开始执行操作后，每次操作都会使L的值变为L~L+9之间（左边污染部分设为0或右边设为9不变，左边设为9或右边设为0变成L+9）。注：L变后会也会对应的改变R，总体的改变是每次操作使R-L减少9.如果（L+R）>0，第一个玩家肯定会选择继续增大L，将L变为L+9，之后的第二个玩家为了消除影响，会把R变为R-9，但这永远都只是消除影响，回到初始状态，赢不了，（L+R）<0时候的情况也一样。
核心就是：第一个选手把局势破坏，而第二个选手只能填前一个的坑，永远无法改变局势，既然局势一开始赢不了，那就永远赢不了。
大概就是左边的数减右边的数得到一个差值，Mono要尽力增大差值的绝对值，而Bicarp要把差值变成0.刚开始二者不断消耗左边和右边的？直到只有一边剩下？。如果这个时候差值==？的数量/29，就是Bicarp赢，否则就是Mono赢。当差值大于？/29时Mono可以每次出0，这样Bicarp最大只能出9，无法减去所有的差值，差值小于？/2*9时同理。（我怎么又不懂自己在说什么了）
代码
#include <bits/stdc++.h>
using namespace std;
#define MWIN printf("Monocarp")
#define BWIN printf("Bicarp")
int n;
char str[200100];
int suml=0,sumr=0;
int lq=0,rq=0;
inline int abs(int x){
return (x>0)?x:-x;
}
int main(){
cin>>n;
scanf("%s",str);
for(int i = 0;i < n/2;i++){
if(str[i]>='0'&&str[i]<='9')suml+=str[i]-'0';
else lq++;
}
for(int i = n/2;i < n;i++){
if(str[i]>='0'&&str[i]<='9')sumr+=str[i]-'0';
else rq++;
}
//debug
//printf("%d %d %d %d\n",suml,sumr,lq,rq);
if(suml==sumr){
lq==rq ? BWIN : MWIN ;
}
else{
(suml-sumr==(rq-lq)/2*9) ? BWIN : MWIN ;
}
return 0;
}（同样有的地方还可以优化优化，但我懒得写了emm）
E. Marbles
F. Radio Stations
两道不会的题，大佬的题解也看不懂，以后再说吧QWQ
评论 (0)