【codeforces 791C】Bear and Different Names
and Codeforces different names
2023-09-14 09:03:47 时间
【题目链接】:http://codeforces.com/contest/791/problem/C
【题意】
给你n-k+1个限制
要求
a[i]..a[i]+k-1里面有相同的元素,或全都不同;
让你输出可能的一个序列
【题解】
先找到YES的一段
(找不到就全都输出一样的);
然后以这段YES作为种子
假设YES的段为pos..pos+k-1
往左往右构造
如果往左构造的话
就是for (int i = pos-1;i>=1;i–)
接下来要给第i个位置确定数字;
则如果i..i+k-1为YES的话
就取[i..i+k-1]中最小的未出现的那个数字;
如果i..i+k-1为NO的话
就取ans[i]=ans[i+k-1];
这样
ans[i..i+k]全都是不一样的;
就不会对再往左的答案造成影响.
往右的话
YES的情况相同
NO的情况变成ans[i]取ans[i-k+1]了.
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 50 + 20;
int n, k, cnt1, po;
int ok[N], ans[N];
int bo[N];
char s[6];
string tar[N];
void in()
{
rei(n), rei(k);
rep1(i, 1, n - k + 1)
{
scanf("%s", s);
if (s[0] == 'N')
ok[i] = 0;
else
{
ok[i] = 1;
cnt1++;
po = i;
}
}
}
void zhitrue(int pos, int l, int r)
{
rep1(i, 0, n)
bo[i] = 0;
rep1(i, l, r)
bo[ans[i]]++;
int x = 0;
while (bo[x]) x++;
ans[pos] = x;
}
void zhifalse(int pos, int l, int r,int p)
{
if (p == 1)
{
ans[pos] = ans[r];
}
else
{
ans[pos] = ans[l];
}
}
void ga()
{
if (cnt1 == 0)
{
rep1(i, 1, n)
ans[i] = 1;
}
else
{
rep1(i, po, po + k - 1)
zhitrue(i, po, po + k - 1);
rep2(i, po - 1, 1)
{
if (ok[i])
zhitrue(i, i, i + k - 1);
else
zhifalse(i, i, i + k - 1,1);
}
rep1(i, po + k, n)
{
if (ok[i])
zhitrue(i, i - k + 1, i);
else
zhifalse(i, i - k + 1, i,0);
}
}
}
void init()
{
rep1(i, 1, 26)
{
char t = i + 'A' - 1;
tar[i] = "";
tar[i] += t;
tar[i] = t;
}
rep1(i, 1, 24)
{
char t1 = i + 'A' - 1, t2 = i + 'a' - 1;
tar[i + 26] = "";
tar[i + 26] += t1;
tar[i + 26] += t2;
}
}
void o()
{
rep1(i, 1, n)
{
cout << tar[ans[i]];
if (i == n)
puts("");
else
putchar(' ');
}
}
int main()
{
//freopen("F:\\rush.txt", "r", stdin);
init();
in();
ga();
o();
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
相关文章
- Net 4.5 WebSocket 在 Windows 7, Windows 8 and Server 2012上的比较以及问题
- codeforces Gargari and Bishops(很好的暴力)
- codeforces Fedor and New Game
- [Javascript] Getter and Setter Abstractions
- [Javascript] Combine Objects with Object.assign and Lodash merge
- [TypeScript] Interface and Class
- Mobility Model and Routing Model about the ONE
- [Compose] 8. A curated collection of Monoids and their uses
- Atitit Major island groups and archipelagos 主要的岛群和群岛目录资料目录1. 岛群 波利尼西亚(Polynesia, 美拉尼西亚(Melanesia,
- attilax.java 注解的本质and 使用最佳实践(3)O7
- 【Codeforces 476C】Dreamoon and Sums
- 【31.58%】【codeforces 719B】 Anatoly and Cockroaches
- 【13.77%】【codeforces 734C】Anton and Making Potions
- 【20.19%】【codeforces 629D】Babaei and Birthday Cake
- 【30.23%】【codeforces 552C】Vanya and Scales
- 【39.66%】【codeforces 740C】Alyona and mex
- 【codeforces 548C】Mike and Frog
- 【codeforces 752B】Santa Claus and Keyboard Check
- 【codeforces 798C】Mike and gcd problem
- 【codeforces 514C】Watto and Mechanism(字典树做法)
- 【codeforces 449C】Jzzhu and Apples
- On Memory Leaks in Java and in Android.
- Codeforces 437E The Child and Polygon(间隔DP)
- 论文解读(FGSM)《Explaining and Harnessing Adversarial Examples》
- 215:vue+openlayers 使用new WFS加载数据,通过like,and,equalTo来过滤数据
- 075:vue+openlayers: Drag-and-Drop拖拽文件解析显示图形(代码示例)
- PAT 1119 Pre- and Post-order Traversals [二叉树遍历][难]