codeforces #373 div2题解
这场比赛充分说明了一个问题：读题大法好+模拟大法好！有个题好像数据还是标程有问题，最后给删掉了
所有只有ABCE四个题
这个题结果成了最“好”得分的题！
如果手速快，并且敢去hack，相当于赚了1000分的C，而且稳得分
注意0和15的坑点就好了呀~~~
这个题比赛场上一直wa4：最后竟然不去重新读题也是自己蠢
In one turn he can either swap any two cockroaches, or take any single cockroach and change it's color.
这句话是关键句子：意思是说：要么可以改变一个值，要么可以交换任意的两个值
那么，我们可以统计r在奇数位置上的个数，r在偶数位置上的个数，b在奇数位置上的个数，b在偶数位置上的个数
最终的答案只可能是两种情况：
第一种：r在偶数&&b在奇数：那么，r在奇数位置需要改变，b在偶数位置需要改变。取这两个数的最大值就是方案数目（两个数的较小值是交换的次数，较大-较小是改变的次数）
第二种同理
那么，这就是一个O（n）的暴力循环贪心算法
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d",&len)!=EOF){
scanf("%s",s);
a=b=c=d=0;
for(int i=0;i<len;i++)
if (s[i]=='r'){
if (i%2) a++;
else b++;
}
else{
if (i%2) c++;
else d++;
}
ans=maxn;
ans=min(max(b,c),ans);
ans=min(max(a,d),ans);
printf("%d\n",ans);
}
return 0;
}
C题：718A
这个题是个模拟好题：也涉及到了贪心的数学思路。比赛的时候，被最后的大数据卡超时（其实改了一句代码就能过，很遗憾）
题意：我们对于一个总共n位的小数（小数点占一位），可以进行K次舍入操作（该操作的位置一定在小数点右侧），求K次操作之后的最大值
Each second, he can ask his teacher to round the grade at any place after the decimal point (also, he can ask to round to the nearest integer).
但是进位可以往整数位置上进
贪心：求最大值：那么一定要进位！而且一定要选择越大的数值权值来进位
意思是说，我们可以从前往后扫描，找到第一个数位值不小于5的点
然后模拟向前进位
注意：超时的点在这：我们需要在向前进位的时候判断
如果进位的全过程中，找不到一个数值不小于5的点，那么就可以退出K次循环了（因为没有进位了，再循环也改变不了值的大小）
如果找到了，说明进位也结束了，因为不可能找到多个值
在进位的过程中，注意几个特殊的数据：
8 100
2.444445
10 100
9.99999999
5 100
1.444一直可以进位的，进位之后整数要变长一位的，从一开始就进位不了的
考虑了这几种情况，相信就比较好写模拟了吧
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+50;
int len,k,pos,numpos;
char s[maxn];
char t[maxn];
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&len,&k)!=EOF){
scanf("%s",s);
int i,j;
for(i=0;;i++)
if (s[i]=='.'){
pos=i;
break;
}
for(j=i;j<len-1;j++) s[j]=s[j+1];
len--;
numpos=0;
while(k--){
bool flag=false;
for(i=max(pos,numpos);i<len&&s[i]!='#';i++)
if (s[i]>='5'){
flag=true;
break;
}
if (!flag) break;
s[i]='#';
for(j=i-1;j>=0;j--){
if (s[j]!='9'){
s[j]=s[j]+1;
if (s[j]>='5') numpos=j;
break;
}
else{
s[j]='0';
if (s[j-1]!='9'){
s[j-1]=s[j-1]+1;
if (s[j-1]>='5') numpos=j;
break;
}
}
}
//for(i=0;i<len;i++) printf("%c",s[i]);cout<<endl;
}
//for(i=0;i<len;i++) printf("%c",s[i]);cout<<endl;
int templen=0;
for(i=0;s[i]!='#'&&s[i]!='$';i++) templen++;
//printf("%d %d\n",len,templen);
len=min(len,templen);
//printf("%d\n",len);
bool flag=false;
for(i=0;i<len;i++)
if (s[i]!='0'){
flag=true;
break;
}
if (!flag){
printf("1");
for(int i=0;i<len;i++) printf("0");
puts("");
continue;
}
if (len>pos){
for(i=0;i<pos;i++) printf("%c",s[i]);
printf(".");
for(i=pos;i<len;i++) printf("%c",s[i]);
puts("");
}
else{
for(i=0;i<len;i++) printf("%c",s[i]);
for(i=len;i<pos;i++) printf("0");
puts("");
}
}
return 0;
}
E题：718C
这个题是个很好的题：综合了我不熟悉的两个方向：线段树+矩阵
其实思路还蛮简单的：
有很多个查询：那么用树状数组或者线段树来维护
有Fib数列：用矩阵来搞快速幂
只是线段树的节点是个矩阵，从来没有这样去想过
#include<bits/stdc++.h>
using namespace std;
#define LL __int64
const int N=2;
const int mod=1e9+7;
struct Martix{
LL arr[N][N];
Martix(int v=0){
memset(arr,0,sizeof(arr));
arr[0][0]=arr[1][1]=v;
}
};
Martix operator * (Martix L,Martix R){
Martix ret;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
(ret.arr[i][j]+=L.arr[i][k]*R.arr[k][j])%=mod;
return ret;
}
Martix operator + (Martix L,Martix R){
Martix ret;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
(ret.arr[i][j]+=L.arr[i][j]+R.arr[i][j])%=mod;
return ret;
}
bool operator == (Martix L,Martix R){
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if (L.arr[i][j]!=R.arr[i][j]) return false;
return true;
}
Martix fir(){
Martix ret;
ret.arr[0][0]=0;
ret.arr[0][1]=1;
ret.arr[1][0]=1;
ret.arr[1][1]=1;
return ret;
}
Martix power(Martix x,LL n){
Martix ret(1);
while(n){
if (n&1) ret=ret*x;
x=x*x;
n>>=1;
}
return ret;
}
#define root 1,1,n
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define Now int o,int l,int r
#define Mid int m=(l+r)>>1
const int maxn=112345;
Martix info[maxn<<2],lazy[maxn<<2];
int arr[maxn];
void segInit(Now){
if (l==r){
info[o]=power(fir(),arr[l]);
return;
}
Mid;
segInit(lson);
segInit(rson);
info[o]=info[o<<1]+info[o<<1|1];
lazy[o]=Martix(1);
}
void seter(int o,Martix v){
lazy[o]=lazy[o]*v;
info[o]=info[o]*v;
}
void pushdown(Now){
if (l!=r){
seter(o<<1,lazy[o]);
seter(o<<1|1,lazy[o]);
}
lazy[o]=Martix(1);
}
void update(Now,int ul,int ur,Martix x){
if (ul<=l&&r<=ur){
seter(o,x);
return;
}
Mid;
if (!(lazy[o]==Martix(1))) pushdown(o,l,r);
if (ul<=m) update(lson,ul,ur,x);
if (ur>m) update(rson,ul,ur,x);
info[o]=info[o<<1]+info[o<<1|1];
}
Martix query(Now,int ql,int qr){
if (ql<=l&&r<=qr) return info[o];
Mid;
if (!(lazy[o]==Martix(1))) pushdown(o,l,r);
Martix ret;
if (ql<=m) ret=ret+query(lson,ql,qr);
if (qr>m) ret=ret+query(rson,ql,qr);
return ret;
}
int main(){
//freopen("input.txt","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
segInit(root);
int op,l,r,v;
while(m--){
scanf("%d%d%d",&op,&l,&r);
if (op==1){
scanf("%d",&v);
update(root,l,r,power(fir(),v));
}
else{
printf("%I64d\n",query(root,l,r).arr[1][0]);
}
}
}
return 0;
}
航天九院公司福利 5人发布