A、环鸽的CHONG
不会算复杂度（现在也不会）
大概做法就是找到一个在当前区间只出现过一次的数字，然后分治两边。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
int pre[MAXN], nex[MAXN];
int a[MAXN];
map<int, int>pos1, pos2;
bool dfs(int l, int r)
{
if (l >= r)
return true;
int q = l, w = r;
while (q <= w)
{
if (pre[q] < l && r < nex[q])
return dfs(l, q - 1) && (dfs(q + 1, r));
q++;
if (pre[w] < l && r < nex[w])
return dfs(l, w - 1) && (dfs(w + 1, r));
w--;
if (q > w)
return false;
}
return false;
}
int main()
{
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
{
sc("%d", &a[i]);
pre[i] = pos1[a[i]];
pos1[a[i]] = i;
}
for (int i = n; i >= 1; i--)
{
if (pos2[a[i]] == 0)
{
nex[i] = n + 1;
pos2[a[i]] = i;
}
else
{
nex[i] = pos2[a[i]];
pos2[a[i]] = i;
}
}
if (dfs(1, n))
pr("chong");
else
pr("fuchong");
}
B、环鸽的数列
由于格式存在问题，还是贴网址吧。
// F_n = \frac{1}{\sqrt{17}}*((\frac{3+\sqrt{17}}{2})^n-(\frac{3-\sqrt{17}}{2})^n)
// F_n = inv_sqrt17*(x_0^n-x_1^n)
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1,op
#define rson mid+1,right,k<<1|1,op
#define imid int mid=(left+right)>>1;
using namespace std;
const int MAXN = 1e5 + 5;
const ll mod = 998244353;
const ll sqrt17 = 473844410;
const ll inv_sqrt17 = 438914993;
const ll x[2] = { 736044383,262199973 };
struct node
{
int l;
int r;
ll mark;
ll sum;
}que[MAXN * 4][2];
ll a[MAXN];
ll facq[MAXN][2]; //power(x[op],i)
const ll inv[2] = { 932694360,315111081 }; //power(x[op]-1,mod-2)
void init()
{
facq[0][0] = 1;
facq[0][1] = 1;
for (int i = 1; i < MAXN; i++)
{
facq[i][0] = facq[i - 1][0] * x[0] % mod;
facq[i][1] = facq[i - 1][1] * x[1] % mod;
}
}
ll power(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll calcnth(ll a1, ll n, int op)
{
ll an = a1 * facq[n - 1][op] % mod;
return an;
}
ll calcsum(ll a1, ll n, ll op)
{
ll q = x[op];
ll an = a1 * facq[n - 1][op] % mod;
ll ans = (an * q % mod - a1 + mod) * inv[op] % mod;
return ans;
}
void up(int k, int op)
{
que[k][op].sum = (que[k << 1][op].sum + que[k << 1 | 1][op].sum) % mod;
}
void down(int k, int op)
{
if (que[k][op].mark)
{
que[k << 1][op].mark = (que[k << 1][op].mark + que[k][op].mark) % mod;
que[k << 1][op].sum = (que[k << 1][op].sum + calcsum(que[k][op].mark, (que[k << 1][op].r - que[k << 1][op].l + 1), op)) % mod;
ll rst = calcnth(que[k][op].mark, que[k << 1][op].r - que[k << 1][op].l + 1 + 1, op);
que[k << 1 | 1][op].mark = (que[k << 1 | 1][op].mark + rst) % mod;
que[k << 1 | 1][op].sum = (que[k << 1 | 1][op].sum + calcsum(rst, (que[k << 1 | 1][op].r - que[k << 1 | 1][op].l + 1), op)) % mod;
que[k][op].mark = 0;
}
}
void build(int left, int right, int k, int op)
{
que[k][op].l = left;
que[k][op].r = right;
que[k][op].mark = 0;
que[k][op].sum = 0;
if (left == right)
{
que[k][op].sum = 0;
return;
}
imid;
build(lson);
build(rson);
up(k, op);
}
void update(int left, int right, int k, int op, int ql, int qr, ll val)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
ll st = calcnth(val, left - ql + 1, op);
que[k][op].mark = (que[k][op].mark + st) % mod;
que[k][op].sum = (que[k][op].sum + calcsum(st, que[k][op].r - que[k][op].l + 1, op)) % mod;
return;
}
down(k, op);
imid;
update(lson, ql, qr, val);
update(rson, ql, qr, val);
up(k, op);
}
ll query(int left, int right, int k, int op, int ql, int qr)
{
if (qr < left || right < ql)
return 0;
if (ql <= left && right <= qr)
return que[k][op].sum;
down(k, op);
imid;
return (query(lson, ql, qr) + query(rson, ql, qr)) % mod;
}
int main()
{
init();
int n, m;
sc("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
sc("%lld", &a[i]);
a[i] = (a[i] + a[i - 1]) % mod;
}
build(1, n, 1, 0);
build(1, n, 1, 1);
while (m--)
{
int op, ql, qr;
sc("%d%d%d", &op, &ql, &qr);
if (op == 1)
{
update(1, n, 1, 0, ql, qr, x[0]);
update(1, n, 1, 1, ql, qr, x[1]);
}
else
{
ll ans1 = query(1, n, 1, 0, ql, qr);
ll ans2 = query(1, n, 1, 1, ql, qr);
ll ans = inv_sqrt17 * (ans1 - ans2 + mod) % mod;
ans = (ans + a[qr] - a[ql - 1] + mod) % mod;
pr("%lld\n", ans);
}
}
}
/*
4 2
0 0 0 0
1 1 1
2 1 1
*/ C、环鸽不会X点
签到
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1
using namespace std;
const int MAXN = 2e5 + 5;
const ll mod = 998244353;
int main()
{
int T;
sc("%d", &T);
while (T--)
{
ll n, k;
sc("%lld%lld", &n, &k);
if (n % 2 != k % 2)
{
pr("No\n");
}
else
{
ll min = 3 * k;
if (n < min)
pr("No\n");
else
pr("Yes\n");
}
}
} D、小C的棋王之路
区间乘，区间加，区间set
三个懒惰标记，处理标记的时候，先处理区间set，再处理区间乘，再处理区间加，如果在区间加有标记的情况下进行区间乘，可以直接将加的标记也乘一下。
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1
using namespace std;
const int MAXN = 2e5 + 5;
struct node
{
int l;
int r;
ll sum;
ll addmark;
ll setmark;
ll mulmark;
}que[MAXN * 4];
ll a[MAXN];
ll mod;
void up(int k)
{
que[k].sum = (que[k << 1].sum + que[k << 1 | 1].sum) % mod;
}
void down(int k)
{
if (que[k].setmark != -1)
{
que[k << 1].mulmark = 1;
que[k << 1 | 1].mulmark = 1;
que[k << 1].addmark = 0;
que[k << 1 | 1].addmark = 0;
que[k << 1].setmark = que[k].setmark;
que[k << 1 | 1].setmark = que[k].setmark;
que[k << 1].sum = que[k].setmark * (que[k << 1].r - que[k << 1].l + 1) % mod;
que[k << 1 | 1].sum = que[k].setmark * (que[k << 1 | 1].r - que[k << 1 | 1].l + 1) % mod;
que[k].setmark = -1;
}
if (que[k].mulmark != 1)
{
que[k << 1].mulmark = que[k << 1].mulmark * que[k].mulmark % mod;
que[k << 1 | 1].mulmark = que[k << 1 | 1].mulmark * que[k].mulmark % mod;
que[k << 1].addmark = que[k << 1].addmark * que[k].mulmark % mod;
que[k << 1 | 1].addmark = que[k << 1 | 1].addmark * que[k].mulmark % mod;
que[k << 1].sum = que[k << 1].sum * que[k].mulmark % mod;
que[k << 1 | 1].sum = que[k << 1 | 1].sum * que[k].mulmark % mod;
que[k].mulmark = 1;
}
if (que[k].addmark != 0)
{
que[k << 1].addmark = (que[k << 1].addmark + que[k].addmark) % mod;
que[k << 1 | 1].addmark = (que[k << 1 | 1].addmark + que[k].addmark) % mod;
que[k << 1].sum = (que[k << 1].sum + que[k].addmark * (que[k << 1].r - que[k << 1].l + 1)) % mod;
que[k << 1 | 1].sum = (que[k << 1 | 1].sum + que[k].addmark * (que[k << 1 | 1].r - que[k << 1 | 1].l + 1)) % mod;
que[k].addmark = 0;
}
}
void build(int left, int right, int k)
{
que[k].l = left;
que[k].r = right;
que[k].setmark = -1;//初值 = -1
que[k].mulmark = 1;
que[k].addmark = 0;
if (left == right)
{
que[k].sum = a[left] % mod;
return;
}
imid;
build(lson);
build(rson);
up(k);
}
void updateadd(int left, int right, int k, int ql, int qr, ll val)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].addmark = (que[k].addmark + val) % mod;
que[k].sum = (que[k].sum + val * (que[k].r - que[k].l + 1)) % mod;
return;
}
imid;
down(k);
updateadd(lson, ql, qr, val);
updateadd(rson, ql, qr, val);
up(k);
}
void updatemul(int left, int right, int k, int ql, int qr, ll val)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].mulmark = que[k].mulmark * val % mod;
que[k].addmark = que[k].addmark * val % mod;
que[k].sum = que[k].sum * val % mod;
return;
}
imid;
down(k);
updatemul(lson, ql, qr, val);
updatemul(rson, ql, qr, val);
up(k);
}
void updateset(int left, int right, int k, int ql, int qr, ll val)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].setmark = val;
que[k].addmark = 0;
que[k].mulmark = 1;
que[k].sum = val * (que[k].r - que[k].l + 1) % mod;
return;
}
imid;
down(k);
updateset(lson, ql, qr, val);
updateset(rson, ql, qr, val);
up(k);
}
ll query(int left, int right, int k, int ql, int qr)
{
if (qr < left || right < ql)
return 0;
if (ql <= left && right <= qr)
return que[k].sum;
imid;
down(k);
return (query(lson, ql, qr) + query(rson, ql, qr)) % mod;
}
int main()
{
int n, m;
sc("%d%d%lld", &n, &m, &mod);
int ql, qr, op; ll val;
for (int i = 1; i <= n; i++)
sc("%lld", &a[i]);
build(1, 200000, 1);
while (m--)
{
scanf("%d", &op);
if (op == 1)//add
{
sc("%d%d%lld", &ql, &qr, &val);
val %= mod;
updateadd(1, 200000, 1, ql, qr, val);
}
else if (op == 2)//mul
{
sc("%d%d%lld", &ql, &qr, &val);
val %= mod;
updatemul(1, 200000, 1, ql, qr, val);
}
else if (op == 3)
{
sc("%d%d%lld", &ql, &qr, &val);
val %= mod;
updateset(1, 200000, 1, ql, qr, val);
}
else if (op == 4)
{
sc("%lld", &val);
val %= mod;
n++;
updateadd(1, 200000, 1, n, n, val);
}
else if (op == 5)
{
sc("%d%d", &ql, &qr);
ll ans = query(1, 200000, 1, ql, qr);
printf("%lld\n", ans);
}
}
} 
京公网安备 11010502036488号