CF 1379_综合_代码迷

Codeforces Round #657 (Div. 2)
这场真的太难打了，对细节处理要求很高。

A Acacius and String

（1500的A题，第一次见）

题意：给一个包含字母和‘？’的字符串，将’?'需要定为某一字母，问是否可以使得’abacaba’存在且只存在一次。
思路：暴力判。

字符串可能原先就有两个或以上’abacaba’
如果只有一个，那么把’?'都填成’z’就好
如果没有，试着去填出一个‘abacaba’，但是，注意填完之后整个串可能出现两个或以上’abacaba’。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
char s[60],ss[60],t[7]={'a','b','a','c','a','b','a'};
int n;
int judge_1(int x,char p[])
{for(int j = 0; j < 7; j++)if(p[x + j] != t[j])return 0;return 1;
}
int judge_2(int x)
{for(int j = 0; j < 7; j++)if(s[x + j] != t[j] && s[x + j] != '?')return 0;for(int i = 1; i <= n; i++)	ss[i] = s[i];for(int j = 0; j < 7;j++)	ss[x + j] = t[j];int cnt =0;for(int i = 1; i <= n - 7 + 1; i++)if(judge_1(i, ss))cnt++;if(cnt == 1)	return 1;return 0;
}
int main(){int T;scanf("%d",&T);while(T){T--;scanf("%d",&n);scanf("%s",s+1);int cnt = 0;for(int i = 1; i <= n - 7 + 1; i++)if(judge_1(i, s))cnt++;if(cnt > 1){printf("No\n");continue;}if(cnt == 1){printf("Yes\n");for(int i = 1; i <= n; i++){ if(s[i]=='?')	printf("z");else	printf("%c",s[i]);} printf("\n");continue;}int i;int flag = 0;for(i = 1; i <= n - 7 + 1; i++)if(judge_2(i))break;if(i <= n - 7 + 1){for(int j = 0; j < 7; j++)	s[i + j] = t[j];printf("Yes\n");for(int i = 1; i <= n; i++){ if(s[i]=='?')	printf("z");else	printf("%c",s[i]);} printf("\n");}else	printf("No\n");}return 0;
}

B Dubious Cyrpto

（1500的B题和1500的A题，哪一个更简单呢？）
题意：给l, r, m，求a, b, c，使得 $l \le a, b, c \le r$ 且存在n使得na+b-c=m。
思路：由 ${l-r} \le {c-b} \le {r-l}$ ，可知， ${m+l-r}\le{na=m+c-b}\le{m+r-l}$ 。枚举a，保证 $\frac{m+r-l}{a}-\frac{m+l-r-1}{a}\ge1$
令 $n=\frac{m+r-l}{a}$
若 $m\le na$ ，b=l；否则，b=r。c=b-m.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define LL long long
using namespace std;
int main()
{int T;LL L, R, l, r, a, b, c, n, m;scanf("%d",&T);while(T){T--;cin>>l>>r>>m;L = m + l -r;R = m + r - l;for(a = l; a <= r; a++)if(R / a - (L - 1)/a >= 1)break;n = R / a;m -= n * a;if(m <= 0)	b = l;else	b = r;c = b - m;cout<<a<<" "<<b<<" "<<c<<endl;}return 0;
}

C Choosing flowers

（这道题2000，不知道为什么……）
题意：给m种物品，每种物品有a_i和b_i两种属性。选取n件物品。对于每一件物品而言，选取k件所获得的价值为a_I+(k-1)b_i。
思路：只有一件物品会选择多于一件，否则不优。其他物品至多选取一件。如果a_i<b_j，那么不会选这种物品。枚举哪一件物品选多件，其他物品a_I大的选一件，小的不选。前缀和+lower_bound处理。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define LL long long
using namespace std;
const int N=1e5+10;
LL sum[N],a[N],b[N],h[N];
int main()
{int T,n,m;scanf("%d",&T);while(T){T--;LL ans=0;scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++){cin>>a[i]>>b[i];h[i] = a[i];}sort(h+1, h+m+1);h[m+1]=0;sum[m+1]=0;for(int i=m;i>0;i--)	sum[i]=sum[i+1]+h[i];ans=sum[max(1,m-n+1)]; for(int i = 1;i<=m;i++){int x=upper_bound(h+1,h+m+1,b[i])-h;if((n-(m-x+1)-1)<0)	continue;LL now=sum[x]+(n-(m-x+1)-1)*b[i]+a[i];if(a[i]>b[i])	now = now - a[i]+b[i];ans=max(ans,now);}cout<<ans<<endl; }return 0; 
} 
/* 2 2 6 5 0 5 4 5 2 2 1 2 1 2 15 3 5 2 4 2 3 1 */

F

题意：给一个2n* 2m的棋盘。该棋盘只有i+j为偶数的地方可以放子。如果一个位置放一枚棋子，那么它周围8联通的位置不能放子。有q组询问，每次占用或解除占用一个格子，询问当前棋盘是否可以放下n*m个棋子。
思路：
将(x, y)-(x+1,y+1)的四个格子看成一个大格，这个大格里面左上角和右下角可以放置棋子。一个大格里只能放置一个棋子，因此每个大格都要放棋子。
一个神奇的结论：
如果存在这样两个大格，(x₁, y₁)在(x₂, y₂)的左上，(x₁, y₁)大格的左上角小格被占据，(x₂, y₂)大格的右下角被占据，那么不合法。因为(x_i, y₁)的大格只能放一枚棋子在右下角小格，相应的(x₁ +1, y₁)、(x₁, y₁ +1)、(x₁+1, y₁+1)这三个大格也只能放右下角……以此类推，(x₂, y₂)的大格也只能放右下角，但是这个位置被占据了，因此不合法。
实现：用set记录每一行的纵坐标。在线段树中，对于大格中左上角的位置，记录该行最小值；对于大格中右下角的位置，记录该行最大值。维护flag，如果左边最小值小于右边最大值，flag为1。询问看flag就好。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
const int N = 2e5 + 10;
set<int>L[N],R[N];
set<int>:: iterator it;
int tr[2][N * 4],flag[N * 4]; 
void build(int x,int l,int r)
{if(l == r){tr[0][x] = N;tr[1][x] = 0;return;}int mid = (l + r) >> 1;build(x * 2, l, mid);build(x * 2 + 1, mid + 1, r);tr[0][x] = min(tr[0][x * 2], tr[0][x * 2 + 1]);tr[1][x] = max(tr[1][x * 2], tr[1][x * 2 + 1]);} 
void update(int opt,int x,int l,int r,int pos,int v)
{if(l == r){tr[opt][x] = v;if(tr[0][x] <= tr[1][x])	flag[x] = 1;else flag[x] = 0;return;}int mid = (l + r) >> 1;if(pos <= mid)	update(opt, x * 2, l, mid, pos, v);else	update(opt, x * 2 + 1, mid + 1, r, pos, v);if(!opt)	tr[opt][x] = min(tr[opt][x * 2], tr[opt][x * 2 + 1]);else	tr[opt][x] = max(tr[opt][x * 2], tr[opt][x * 2 + 1]); if(flag[x * 2] || flag[x * 2 + 1] || tr[0][x * 2] <= tr[1][x * 2 + 1])	flag[x] = 1;else flag[x] = 0;
}
int main()
{int n, m, q, x, y;scanf("%d%d%d", &n, &m, &q);build(1, 1, n);for(int i = 1; i <= n; i++)L[i].insert(N), R[i].insert(0);for(int i = 1; i <= q; i++){scanf("%d%d", &x, &y);if(x%2 == 1 && y%2 == 1){x = x / 2 + 1;y = y / 2 + 1;if(L[x].find(y) != L[x].end())	L[x].erase(y);else	L[x].insert(y);it = L[x].begin();update(0, 1, 1, n, x, *it);if(!flag[1])	printf("YES\n");else printf("NO\n");}elseif(x%2 ==0 && y%2 == 0){x /= 2;y /= 2;if(R[x].find(y) != R[x].end())	R[x].erase(y);else	R[x].insert(y); it = R[x].end();it--;update(1, 1, 1, n, x, *it);if(!flag[1])	printf("YES\n");else	printf("NO\n");}}return 0;}