Codeforces Round #578 (Div. 2) A.B.C.D.E
A. Hotelier
用个数组标记房间有没有人，循环10次即可
/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */
#include<bits/stdc++.h>
#define ll long long
using namespace std;
char ss[100005];
int a[15] = {0};
int main() {
int n;
cin>>n;
cin>>ss;
int len = strlen(ss);
for(int i = 0; i < n; i++) {
if(ss[i] == 'L') {
for(int i = 0; i < 10; i++) {
if(a[i] == 0) {
a[i] = 1;
break;
}
}
}
else if(ss[i] == 'R') {
for(int i = 9; i >=0; i--) {
if(a[i] == 0) {
a[i] = 1;
break;
}
}
}
else {
a[ss[i]-'0'] = 0;
}
}
for(int i = 0; i <= 9; i++){
cout<<a[i];
}
return 0;
}
B.Block Adventure
每次到一个柱子的时候，如果block不够，我们就把袋子里的block把 a[i]补到 a[i+1]-k个, 如果block足够，我们就把多余a[i+1]-k个的部分放到袋子里面，这样是最优的，但是要有个wa点，a[i+1]-k可能为负数，也就当柱子上没有block,我们取不了，加个判断即可
/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main() {
int t;
for(cin>>t; t ; t--) {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int f = 0;
for(int i = 0; i < n-1; i++) {
if(a[i] + k >= a[i+1]){
m += a[i] - (max(a[i+1] - k, 0));
}else {
int ans = a[i+1] - a[i] - k;
if(ans <= m){
m -= ans;
} else {
f = 1;
break;
}
}
}
if(f == 1){
printf("NO\n");
}else {
printf("YES\n");
}
}
return 0;
}
C.Round Corridor
先求出n和m的最大公因数gcd, 这样n走廊每 n/gcd 块区域 和 m走廊每 m/gcd块区域一定可以互通， 其他的一定会隔绝，判断两个位置属不属于同一块区域
代码太长，懒得跟dalao一样精简，这样容易看懂理解
/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
ll n, m, q;
cin>>n>>m>>q;
ll a, b, c, d;
ll gc = __gcd(n, m);
ll nn = n/gc;
ll mm = m/gc;
for(int i = 0; i < q; i++) {
scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
if(a == 1 && c == 1) {
ll x = b/nn - (b%nn==0?1:0);
ll y = d/nn - (d%nn==0?1:0);
if(x == y) {
puts("YES");
} else {
puts("NO");
}
} else if(a == 2 && c == 2) {
ll x = b/mm - (b%mm==0?1:0);
ll y = d/mm - (d%mm==0?1:0);
if(x == y) {
puts("YES");
} else {
puts("NO");
}
} else if(a == 1 && c == 2) {
ll x = b/nn - (b%nn==0?1:0);
ll y = d/mm - (d%mm==0?1:0);
if(x == y) {
puts("YES");
} else {
puts("NO");
}
} else {
ll x = b/mm - (b%mm==0?1:0);
ll y = d/nn - (d%nn==0?1:0);
if(x == y) {
puts("YES");
} else {
puts("NO");
}
}
}
return 0;
}
D.White Lines
疯狂预处理，比赛没get到点，最后去开E了，E也没写好
就是前缀和
举个对行的预处理的操作
先对每一行，如果为W就+1，做一遍前缀和
如果前缀和为n则说明这一行为全W
然后枚举 click 的点，例如枚举(i, j), 则(i,j) - (i+k-1, j+k-1)被我们弄成全W,但是我们判断，如果click(i, j) 该行会不会从非全W变成全W
只要满足1到j-1全W， j+k到n全W， j到j+k-1有B 即可，用前缀和O(E)可以得到
然后我们我们再对得到的结果再进行一次前缀和保存到row数组里面，row[i][j]表示当 1 ~ i 行的 **j到(j+k-1)**列 被弄成全W,会新增多少行全W,然后我们就可以O(E)求出click(i,j)新增多少行全W
列同理预处理
时间复杂度：O( n2)
/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */
#include<bits/stdc++.h>
#define ll long long
#define maxn 2005
using namespace std;
char ss[maxn][maxn];
int sum[maxn][maxn],row[maxn][maxn], col[maxn][maxn], ans[maxn][maxn];
int main() {
int n, k;
cin>>n>>k;
for(int i = 1; i <= n; i++ ) {
scanf("%s", ss[i]+1);
}
int cnt = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
sum[i][j] = sum[i][j-1] + (ss[i][j]=='W'?1:0);//对每一行求前缀和出来
}
if(sum[i][n] == n) {
cnt++;
}
for(int j = 1; j <= n-k+1; j++) {
if(sum[i][j-1] == j-1 && sum[i][n] - sum[i][j+k-1] == n-(j+k-1) && sum[i][j+k-1] - sum[i][j-1] != k) { // 1到j-1全W j+k到n全W j到j+k-1有B
row[i][j] = row[i-1][j] + 1;
} else {
row[i][j] = row[i-1][j];
}
// cout<<row[i][j]<<" ";
}
// puts("");
}
for(int i = 1; i <= n-k+1; i++) {
for(int j = 1; j <= n-k+1; j++) {
ans[i][j] = row[i+k-1][j] - row[i-1][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
sum[j][i] = sum[j-1][i] + (ss[j][i]=='W'?1:0);//对每一列求前缀和出来
}
if(sum[n][i] == n) {
cnt++;
}
for(int j = 1; j <= n-k+1; j++) {
if(sum[j-1][i] == j-1 && sum[n][i] - sum[j+k-1][i] == n-(j+k-1) && sum[j+k-1][i] - sum[j-1][i] != k) { // 1到j-1全W j+k到n全W j到j+k-1有B
col[j][i] = col[j][i-1] + 1;
} else {
col[j][i] = col[j][i-1];
}
}
}
for(int i = 1; i <= n-k+1; i++) {
for(int j = 1; j <= n-k+1; j++) {
ans[j][i] += col[j][i+k-1] - col[j][i-1];
}
}
int maxx = 0;
for(int i = 1; i <= n-k+1; i++) {
for(int j = 1; j <= n-k+1; j++) {
maxx = max(maxx, ans[i][j]);
}
}
cout<<maxx+cnt<<endl;
return 0;
}
E.Compress Words
先对第一个做hash处理，并且作为答案串
然后接下来每一个字符串做hash处理，再拿其前缀与答案串后缀继续判断，相同部分不加到答案串里面，每次加入答案串的字符都要做一次hash处理
base:13331
mod:917120411
/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e6+5;
const long long mod = 917120411LL;
ll xp[maxn],ha[maxn],ans[maxn];
char s[maxn], c[maxn];
int len1,len,tot;
void init() {//预处理
xp[0] = 1;
for(int i = 1; i < maxn; ++i) {
xp[i] = xp[i-1] * 13331 % mod;
}
}
int makehash() {//对答案进行hash处理
int len = strlen(s+1);
ha[0] = 0;
ha[1] = s[1];
for(int i = 2; i <= len; ++i) {
ha[i] = (ha[i-1] * 13331 +s[i])%mod;
}
return len;
}
ll gethash(int now, int l) {//返回从now开始长度为l的字符串的哈希值
return (ha[l + now - 1] - (ha[now-1] * xp[l]) % mod + mod) % mod;
}
int main() {
int n;
cin>>n;
init();
scanf("%s", s+1);
len = makehash();
for(int j = 2; j <= n; j++) {
scanf("%s", c+1);
len1 = strlen(c+1);
ans[1] = c[1];
for(int i = 2; i <= len1; ++i) {
ans[i] = (ans[i-1] * 13331+c[i]) % mod;
}
tot = 1;
for(int i = 1; i <= min(len1, len); i++) {//暴力判断前后缀相同部分
if(ans[i] == gethash(len-i+1, i)) {
tot = i + 1;
}
}
for(int i = tot; i <= len1; i++) {
len++;
s[len] = c[i];
ha[len] = (ha[len-1] * 13331 + s[len]) % mod;
}
s[len+1] = '\0';
}
printf("%s",s+1);
return 0;
}
有条件还是搬吧
