Practice I
前言
已经被大佬们虐死了 T^T
接下来攻好长好长一段时间的Practice系列
刷题呢，个人感觉，没学算法那么痛苦，而且还快！
（这个系列题目不给截图）
Birthday Cake - UVA - 10167
题意
求一条直线Ax+By=0，将平面上的点等分
思路
今天训练的题目，个人能接受的算法真的是活久见！
看dalao用随机数的方法AC
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 200 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N][2];
bool judge(int A, int B, int n){
int cnt1 = 0, cnt2 = 0;
for(int i = 0; i < n; i++){
if(A*a[i][0] + B*a[i][1] == 0) return false;
if(A*a[i][0] + B*a[i][1] < 0) cnt1++;
else cnt2++;
}
return cnt1 == cnt2;
}
int main(){
int n;
while(scanf("%d", &n) && n){
n <<= 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < 2; j++){
scanf("%d", &a[i][j]);
}
}
int A, B;
while(true){
A = rand()%1001 - 500;
B = rand()%1001 - 500;
if(judge(A, B, n)) break;
}
printf("%d %d\n", A, B);
}
}
Zebras - CodeForces - 950C
题意
找出方法使得给定字符串能由若干个形如0,010,01010,…的子序列不重叠构成，输出序列总数，每条序列的大小和其上元素的相应位置，不能则输出-1
思路
填5个月前的坑
个人开了两个队列维护着做，看到0则看看能不能接上已有的1，不能则新建序列，看到1则看看接上已有的0，不能则无解
dalao的代码特别神仙！各位dalao可以百度这题题号看看dalao是怎么写的
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 2e5 + 15;
const int inf = 0x3f3f3f3f;
char s[N];
vector<int> vec[N];
queue<int> quezero, queone;
int main(){
while(~scanf("%s", s)){
for(int i = 0; i < N; i++) vec[i].clear();
while(!quezero.empty()) quezero.pop();
while(!queone.empty()) queone.pop();
int tot = 0;
bool flag = true;
for(int i = 0; s[i]; i++){
if(s[i] == '0'){
if(!queone.empty()){
int idx = queone.front();
queone.pop();
vec[idx].push_back(i + 1);
quezero.push(idx);
}else{
vec[++tot].push_back(i + 1);
quezero.push(tot);
}
}else{
if(quezero.empty()){
flag = false;
break;
}
int idx = quezero.front();
quezero.pop();
vec[idx].push_back(i + 1);
queone.push(idx);
}
}
if(!queone.empty()){
flag = false;
}
if(flag){
printf("%d\n", tot);
for(int i = 1; i <= tot; i++){
printf("%d", vec[i].size());
for(int j = 0; j < vec[i].size(); j++){
printf(" %d", vec[i][j]);
}
puts("");
}
}else{
puts("-1");
}
}
return 0;
}
Mister B and PR Shifts - CodeForces - 820D
题意
输出序列循环同构中 | p[i] - i | 的最小值，以及循环次数
思路
看了dalao的题解才懂了（大概七成多把，懵懵懂懂），具体看代码注释
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e6 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N], cnt[N];
int main(){
int n;
while(~scanf("%d", &n)){
//cnt[i]:位移i次到达本身的数的数量，到达此点后再位移会由sub变为add（含义见下句）
memset(cnt, 0, sizeof(cnt));
int add = 0, sub = 0; //add:下次位移会增加1的数量，sub:反之
ll sum = 0; //当前和
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
sum += (int)fabs(a[i] - i);
if(i < a[i]){
cnt[a[i] - i]++;
sub++;
}else{
cnt[(a[i] - i + n)%n]++;
add++;
}
}
ll anssum = sum;
int ansidx = 0;
for(int i = 1; i <= n; i++){
// + add - sub - 1：其中-1是因为最后一位要调到第一位，但是其中add把它算多了一次
// 因为最后一位下标为n，而a[i] <= n，因此算多的部分必定给了add
sum = sum + add - sub - 1 - (n - a[n - i + 1]) + (a[n - i + 1] - 1);
// 分两种情况：
// ① a[n - i + 1] != 1，那么调到头由add变为sub，所以 add - 1, sub + 1
// ② a[n - i + 1] == 1，那么掉到头由add变为add，不变
// 但是呢，调过去后a[1] == 1，因此算在了cnt[i]中
// 所以 +(cnt[i] - 1) , -(cnt[i] - 1)
// 化简后相同
add = add + cnt[i] - 1;
sub = sub - cnt[i] + 1;
if(anssum > sum){
anssum = sum;
ansidx = i;
}
}
printf("%lld %d\n", anssum, ansidx);
}
return 0;
}
Games on a CD - CodeForces - 727E
题意
顺时针给出一环形字符串，再给定g个长度为k的字符串，问环形字符串能否从由g个字符串中的某一些不重叠组成，能则从任意位置开始顺时针输出字符串的位置，不能输出NO
思路
本题似乎卡Hash，dalao们好多都用双Hash做的，蒟蒻不会 _(:з」∠)_
用Hash结果WA了10发，最后用AC自动机过的，官方题解给用的是后缀树
将g个字符串加入AC自动机中，然后用环形字符串跑AC自动机，匹配得到的位置就更新一下f数组（其中存的是g个字符串各自所在的位置），最后穷举f数组，如果其中答案都不重复则YES，否则NO
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2e6 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
bool used[N];
char s[N], p[N];
int nxt[N][26];
int fail[N];
int pos[N];
int f[N];
int tot;
inline void init(){
memset(nxt, -1, sizeof(nxt));
memset(fail, 0, sizeof(fail));
memset(pos, -1, sizeof(pos));
tot = 1;
}
void push(int pp, char* p){
int rt = 0;
for(int i = 0; p[i]; i++){
int idx = p[i] - 'a';
if(nxt[rt][idx] == -1){
nxt[rt][idx] = tot++;
}
rt = nxt[rt][idx];
}
pos[rt] = pp;
}
int que[N], head, tail;
void setFail(){
for(int j = 0; j < 26; j++){
if(nxt[0][j] == -1) nxt[0][j] = 0;
else que[tail++] = nxt[0][j];
}
while(head != tail){
int rt = que[head++];
for(int j = 0; j < 26; j++){
if(nxt[rt][j] != -1){
fail[nxt[rt][j]] = nxt[fail[rt]][j];
que[tail++] = nxt[rt][j];
}else{
nxt[rt][j] = nxt[fail[rt]][j];
}
}
}
}
void query(char* s, int k){
int rt = 0;
for(int i = 0; s[i]; i++){
int idx = s[i] - 'a';
rt = nxt[rt][idx];
f[i - k + 1] = pos[rt];
}
}
int main(){
int n, plen;
while(~scanf("%d%d", &n, &plen)){
init();
int slen = n*plen;
scanf("%s", s);
for(int i = 0; i < slen; i++){
s[i + slen] = s[i];
}
slen <<= 1;
int k;
scanf("%d", &k);
for(int i = 1; i <= k; i++){
scanf("%s", p);
push(i, p);
}
setFail();
query(s, plen);
int ansp = -1;
for(int i = 0; i < plen; i++){
int j, q;
for(j = i, q = 0; q < n; j += plen, q++){
if(f[j] == -1 || used[f[j]]) break;
used[f[j]] = true;
}
if(q == n){
ansp = i;
break;
}
for(; j >= i; j -= plen) used[f[j]] = false;
}
if(ansp == -1) puts("NO");
else{
puts("YES");
for(int i = ansp, q = 0; q < n; i += plen, q++){
printf("%d", f[i]);
if(q < n - 1) putchar(' ');
}
puts("");
}
}
return 0;
}
Replacement - CodeForces - 570C
题意
不断更新给定字符串中给定位置的字符，询问每次操作后把相邻”..”合并为一个”.”所需的次数
思路
初始答案是 连成一块的”.”的数量 - 1 的和
每次更新时，若替代的字符和被替代的字符不都是”.”或不都是字母，则找找它的左一位和右一位（若有），若有则对应+1(-1)
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 3e5 + 15;
char s[N];
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
s[0] = s[n + 1] = 'a';
scanf("%s", s + 1);
int ans = 0;
for(int i = 2; i <= n; i++){
if(s[i] == '.' && s[i - 1] == '.'){
ans++;
}
}
while(m--){
int pos;
char ch;
scanf("%d %c", &pos, &ch);
if(s[pos] == '.' && ch != '.'){
if(s[pos - 1] == '.') ans--;
if(s[pos + 1] == '.') ans--;
}else if(s[pos] != '.' && ch == '.'){
if(s[pos - 1] == '.') ans++;
if(s[pos + 1] == '.') ans++;
}
s[pos] = ch;
printf("%d\n", ans);
}
}
return 0;
}
String Reconstruction - CodeForces - 828C
题意
要求构造一个字符串，根据给定的一些字符串和其所在位置，构造出字典序最小的字符串
思路
首先开数组标记字符串所在原输入的位置，若由冲突则保留长度最大的
然后跑一遍得到字符串长度最大值
根据这一最大值，构造字符串，构造过程中，遇到有标记则不断尝试向右延伸，即比较当前所能达到的右边界和该标记所能达到的右边界值，若能向右延伸则切换到该标记所在的字符串，若遇到无标记且当前串被填写完了，则填写字母’a’（满足字典序最小），直到到达长度最大值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e6 + 15;
int mp[N];
int maxlen[N];
char ans[N];
string s[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int m;
while(cin >> m){
memset(maxlen, 0, sizeof(maxlen));
memset(mp, -1, sizeof(mp));
memset(ans, 0, sizeof(ans));
int endpos = 0;
for(int i = 1; i <= m; i++){
cin >> s[i];
int slen = s[i].size();
int k;
cin >> k;
while(k--){
int tmp;
cin >> tmp;
if(maxlen[tmp] < slen){
maxlen[tmp] = slen;
mp[tmp] = i;
}
endpos = max(endpos, tmp + maxlen[tmp] - 1);
}
}
int r = 1;
int cur = mp[1];
int j = 0;
for(int i = 1; i <= endpos; i++){
if(mp[i] != -1 && r < i + s[mp[i]].size()){
r = i + s[mp[i]].size();
cur = mp[i];
j = 0;
}
if(j < s[cur].size()){
ans[i] = s[cur][j];
j++;
}
}
r--;
//cout << "endpos:" << endpos << endl;
for(int i = 1; i <= endpos; i++){
if(ans[i] == 0) cout << 'a';
else cout << ans[i];
}
cout << endl;
}
return 0;
}
