A. Set
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int t;
scanf("%d",&t);
while(t--) {
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",max(0,r/k-l+1));
}
return 0;
}
B. Replacement
操作就相当于删除R[i]^1
只要原序列S有0和1，那么肯定有相邻的地方。
反之，直接输出NO。
不用考虑具体删哪里，（实际上是删相邻的01之间的一个）无法删除了就是NO
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char str1[100005],str2[100005];
int main() {
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
scanf("%s",str1);
scanf("%s",str2);
int len1=strlen(str1),len2=strlen(str2);
int cnt1=0,cnt0=0;
for(int i=0;i<len1;i++) {
if(str1[i]=='1') cnt1++;
else cnt0++;
}
if(cnt1==0||cnt0==0) {
puts("NO");
continue;
}
bool flag=1;
for(int i=0;i<len2;i++) {
if(str2[i]=='1') {
if(!cnt1) {
flag=0;
break;
}
cnt0--;
}
else {
if(!cnt0) {
flag=0;
break;
}
cnt1--;
}
if(cnt0<0||cnt1<0) {
flag=0;
break;
}
}
puts(flag?"YES":"NO");
}
return 0;
}
C. New Rating
题意：选一段区间跳过，然后求最大rating
dp
f[i][0/1/2]分别表示当前到i，到i正在跳过/还没跳过/之前已经跳过 的最大rating
然后转移即可，详见代码。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=3e5+5;
int a[N];
int f[N][3];
//0跳，1没跳过，2跳过
int main() {
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
f[1][0]=0;
f[1][1]=1;
// f[1][2]=0;
if(n==1) {
puts("0");
continue;
}
for(int i=2;i<=n;i++) {
f[i][0]=max(f[i-1][0],f[i-1][1]);
if(a[i]>f[i-1][1])
f[i][1]=f[i-1][1]+1;
else if(a[i]==f[i-1][1])
f[i][1]=f[i-1][1];
else
f[i][1]=f[i-1][1]-1;
int tmp;
if(a[i]>f[i-1][0]) tmp=1;
else if(a[i]==f[i-1][0]) tmp=0;
else tmp=-1;
int tmp2;
if(a[i]>f[i-1][2]) tmp2=1;
else if(a[i]==f[i-1][2]) tmp2=0;
else tmp2=-1;
f[i][2]=max(f[i-1][0]+tmp,f[i-1][2]+tmp2);
// cout<<f[i][0]<<" "<<f[i][1]<<" "<<f[i][2]<<endl;
}
printf("%d\n",max(f[n][2],f[n][0]));
}
return 0;
}
D. Cool Graph
考试时的思路：
找所有的环，一只拆环直到不能拆，
随便找一条边作为基础，将拆出来的单独点，连到基础边上。
拆出来的几个联通块，想得是并查集维护（无敌麻烦）
但不太好处理找环和拆环。
看了题解：
找任意\(du[u]>=2\)的点u，再找它相邻的两个点，输出它们仨。
由于每个操作都会至少减少边数\(1\), 至多\(m\)次操作
一直重复，那么现在图上就不会再出现环了,被拆成了若干条链和独立点。
（这里就解决了前面的问题）
分开存链（边）和独立点。
对于独立点，随便找一条边(a,b)作为基础，将非(a,b)所在联通块的单独点，连到基础边上，注意基础边每次需要换，不能是同一条，要不就连成环了！
对于其他的边，和\(a\)连上就行。
这里至多\(max(n,m)\)次操作
总操作数\(<2*max(n,m)\)
具体实现：
每个点建一个set维护与他相邻的点，然后size就是其度数。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
#define LL long long
using namespace std;
const int N = 200005;
int n, m;
struct node {
int a, b, c;
node(int aa, int bb, int cc) {
a = aa;
b = bb;
c = cc;
}
void print() {
printf("%d %d %d\n", a, b, c);
}
};
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d %d", &n, &m);
//init
vector<set<int>> v(n + 1);
vector<node> ans;
for (int i = 1, x, y; i <= m; i++) {
scanf("%d %d", &x, &y);
v[x].insert(y);
v[y].insert(x);
}
for (int i = 1; i <= n; i++) {
while (v[i].size() >= 2) {
int x = *v[i].begin();
v[i].erase(x);
int y = *v[i].begin();
v[i].erase(y);
v[x].erase(i);
v[y].erase(i);
ans.push_back(node(i, x, y));
if (v[x].find(y) != v[x].end()) {
v[x].erase(y),
v[y].erase(x);
} else {
v[x].insert(y);
v[y].insert(x);
}
}
}
vector<int> singlePoint;
vector<pair<int, int>> p;
for (int i = 1; i <= n; i++) {
if (v[i].size() == 0) {
singlePoint.push_back(i);
} else if (*v[i].begin() > i) {
p.push_back(make_pair(i, *v[i].begin()));
}
}
if (p.size()) {
auto [a, b] = p.back();
p.pop_back();
while (!singlePoint.empty()) {
int x = singlePoint.back();
singlePoint.pop_back();
ans.push_back(node(x, a, b));
b = x;//注意不能每次都合并到相同一条边，会成环，所以换个边
}
for (auto [x, y]: p) {
ans.emplace_back(node(x, y, a));
}
}
printf("%d\n", ans.size());
for (auto x: ans) {
x.print();
}
}
return 0;
}