前言
大家都在洛谷上去找原题吧，洛谷还是不错的qwq
A
因为没有重复的数，我们只要将数据排序，比较两两之间有没有(a_j - a_i == 1 (j > i)) 的，有则输出 (2) , 无则输出 (1)
普及T1难度
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 107
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
int q,n,ans;
int a[N];
void work() {
memset(a, 0, sizeof(a));
n = read();
for(int i=1;i<=n;++i)
a[i] = read();
sort(a+1, a+1+n);
bool flag = 1;
for(int i=1;i<=n-1;++i) {
if(a[i+1]-a[i] == 1) flag = 0;
}
if(flag) puts("1");
else puts("2");
}
int main()
{
q = read();
while(q--) {
work();
}
return 0;
}
B
通过模拟样例我们可以发现序列上有一些环 (这个很好理解吧？拿出纸笔画画qwq)
先预处理一下每个环的长度，和每个点所在环
然后直接输出即可
普及T2？
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 2e5+7;
int n,q,tot;
int p[N],color[N],cnt[N];
void work() {
memset(color, 0, sizeof(color));
tot = 0;
n = read();
for(int i=1;i<=n;++i)
p[i] = read();
for(int i=1,j,sum;i<=n;++i) {
if(!color[i]) {
color[i] = ++tot;
j = p[i], sum = 1;
while(j != i) j = p[j], ++sum, color[j] = tot;
cnt[tot] = sum;
}
}
for(int i=1;i<=n;++i)
printf("%d ",cnt[color[i]]);
putchar('
');
}
int main()
{
q = read();
while(q--) work();
return 0;
}
C
先把十进制转换为三进制
如 (17) -> (1) (2) (2)
从左往右数发现第二位有一个 "(2)"，
再找 "2" 的前面出现的第一个 "(0)" ，把它改为 "(1)"，如果前面没有 "(0)" 了，我们就加一位 (->(1) (1) (2) (2)) (第四位是改动的位置)
再从改动的位置向下把它下面的每一位改为 "(0)" (->(1) (0) (0) (0)) ，这个数我们就找到了
想一想，这样做为什么是对的？
∵ 我们要消除 "(2)" ∴ 最高位上的 "(2)" 是一定要消去的
∴ 找到比这个 "(2)" 高的最近的一位 "0" ，把它改为 "(1)" ，相当于进了一位，故把后面所有的数改为 "(0)"
提高 Day1T1 难度？
Code
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define int long long
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
int n,q;
void work() {
vector<int> num;
n = read(); int t = n;
while(n) num.push_back(n%3), n/=3;
int x = -1LL;
for(int i=num.size()-1;i>=0;--i)
if(num[i] == 2) {
x = i; break;
}
if(x == -1LL) printf("%lld
",t);
else {
num.push_back(0);
for(int i=x+1;i<num.size();++i)
if(!num[i]) {
num[i] = 1;
for(int j=i-1;j>=0;--j) num[j] = 0LL;
break;
}
x = 0LL;
for(int i=num.size()-1;i>=0;--i) x = (x*3) + num[i];
printf("%lld
",x);
}
}
signed main()
{
q = read();
while(q--) work();
return 0;
}
D
USACO原题 如果考场上快点看了这题就好了
如果用贪心+线段树思路是比较简单的。
线段树做两个事情：1.查询区间最大值(当前区间被线段覆盖得最多的这个点，判断是否还能继续加，不能就说明这条边要删去，计入答案)。2.区间加上一个值(如果这个区间加入一条线段，区间的每个点加一)
这个还是比较好理解的吧
纯贪心有点神仙，我不会qwq
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 2e5+7;
int n,k,ans;
vector<int> v;
struct Node {
int l,r,id;
}a[N];
struct Segment_Tree {
int mx[N<<2],lazy[N<<2];
inline int ls(int p) { return p<<1; }
inline int rs(int p) { return p<<1|1; }
inline void push_up(int p) { mx[p] = max(mx[ls(p)], mx[rs(p)]); }
inline void fl(int p,int x) { lazy[p] += x; mx[p] += x; }
inline void push_down(int p) {
fl(ls(p),lazy[p]); fl(rs(p),lazy[p]); lazy[p] = 0;
}
void update(int nl,int nr,int p,int l,int r,int x) {
if(nl<=l && r<=nr) {
fl(p,x); return ;
}
int mid = (l+r)>>1;
if(nl<=mid) update(nl,nr,ls(p),l,mid,x);
if(nr>mid) update(nl,nr,rs(p),mid+1,r,x);
push_up(p);
}
int Query(int ql,int qr,int p,int l,int r) {
if(ql<=l && r<=qr) return mx[p];
int mid = (l+r)>>1, res = 0;
push_down(p);
if(ql<=mid) res = max(res, Query(ql,qr,ls(p),l,mid));
if(qr>mid) res = max(res, Query(ql,qr,rs(p),mid+1,r));
return res;
}
}T;
bool cmp(Node x,Node y) {
return x.r < y.r;
}
int main()
{
n = read(), k = read(); int m = 0;
for(int i=1;i<=n;++i)
a[i].l = read(), a[i].r = read(), m = max(m,a[i].r), a[i].id = i;
sort(a+1, a+1+n, cmp);
for(int i=1;i<=n;++i) {
int l = a[i].l, r = a[i].r;
int maxx = T.Query(l,r,1,1,m);
if(k-maxx>=1) {
T.update(l,r,1,1,m,1);
} else {
v.push_back(a[i].id);
}
}
printf("%d
",(int)v.size());
for(int i=0;i<v.size();++i)
printf("%d ",v[i]);
return 0;
}