T1【color】涂色游戏
【Description】 https://www.luogu.com.cn/problem/P6476
比较水的一道题。
用\(gcd(p_1,p_2)\)和贪心乱搞一通，用裴蜀定理证明，没了。
但是千万千万记得要特判\(k=1\)
时间复杂度：\(O(T\;log\;p)\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
LL a, b, k, T;
LL gcd(LL a,LL b)
{
if(b == 0) return a;
return gcd(b , a % b);
}
int main()
{
cin>>T;
while(T--)
{
scanf("%lld%lld%lld",&a,&b,&k);
if(k == 1)
{
puts("No");
continue;
}
if(a > b)swap(a,b);
LL g = gcd(a,b);
LL t = ((b - g) % a == 0) ? 0 : 1;
if((b - g) / a + t < k)puts("Yes");
else puts("No");
}
return 0;
}
T2【sequence】子序列问题
【Description】 https://www.luogu.com.cn/problem/P6477
暴力
直接枚举\(l,r\)，然后在\(r\)不断加\(1\)的同时，更新此时区间中数字种类个数
时间复杂度：\(O(n^2)\)
期望得分：\(50pts\)
正解
直接求平方似乎不太好操作
\(\because f(l,r)^2=f(l,r)(f(l,r)-1)+f(l,r)\)
不妨设\(F(n)=\sum_{i=1}^n f(i,n)\;,\;g(n)=\sum_{i=1}^n f(i,n)(f(i,n)-1)\)
然后我们只需分别求\(\sum_{i=1}^n F(n),g(n)\)即可
关键是怎么求？
现在给出一个思路：求\(F(n)-F(n-1)\)与\(g(n)-g(n-1)\)
而\(F(n)\)中的每个区间只比\(F(n-1)\)中的区间多了\(a_n\)
所以我们预处理出\(last_n=j\),\(j<n\)且\(a_j=a_n\)(\(j\)是满足这个条件中最靠后的)
因此只有\([last_n+1,n]\)为\(l\)端点的区间才会多出\(a_r\)这个新的数字，产生\(1\)的贡献，总共多产生了\(n-last_n\)的贡献
\(\therefore F(n)-F(n-1)=n-last_n\)
而这个玩意相当于把\([last_n+1,n]\)这段区间执行\(+1\)的操作
而求\(g(n)-g(n-1)\)与\(F\)同理。
\([last_n+1,n]\)为\(l\)端点的区间，多产生\(1\)的贡献。
因此：这些区间的\(f(l,r)(f(l,r)-1)=>f(l,r)(f(l,r)+1)\)
\(\because f(l,r)(f(l,r)+1)-f(l,r)(f(l,r)-1)=2\times f(l,r)\)
所以总共会增长：\(2\times \sum_{i=last_n+1}^n f(i,r)\)
而：\(\sum_{i=last_n+1}^n f(i,r)\)实际是一个区间求和的操作
区间执行\(+1\)，区间求和你想到了什么？
没错，就是线段树。
因此在枚举\(r\)（右端点）的过程中用线段树维护区间修改与和。
注意在修改与求和的顺序。
时间复杂度：\(O(n\;log\;n)\)
期望得分：\(100pts\)
\(code:\)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010, mod = 1000000007;
#define LL long long
#define F(i,a,b) for(int i=a;i<=b;i++)
#define ls(x) x<<1
#define rs(x) x<<1|1
int n, a[N], b[N], ap[N], last[N];
LL tree[N << 2], tag[N << 2], f[N], g[N], res1, res2;
inline void push_up(int root)
{
tree[root] = (tree[ls(root)] + tree[rs(root)]) % mod;
}
void build (int root, int l, int r)
{
if(l==r)
{
return;
}
int mid = (l + r) >> 1;
build(ls(root), l, mid);
build(rs(root), mid+1, r);
push_up(root);
}
inline void change(int root, int l, int r, LL k)
{
tag[root] = (tag[root] + k) % mod;
tree[root] = (tree[root] + (r-l+1) * k % mod) % mod;
}
void push_down(int root, int l, int r)
{
if(tag[root])
{
int mid = (l + r) >> 1;
change(ls(root), l, mid, tag[root]);
change(rs(root), mid+1, r, tag[root]);
}
tag[root] = 0;
}
void Update(int root, int L, int R, int l, int r, LL k)
{
if(l<=L&&R<=r)
{
change(root,L,R,k);
return;
}
push_down(root,L,R);
int mid = (L + R) >> 1;
if(l <= mid) Update(ls(root), L, mid, l, r, k);
if(r > mid) Update(rs(root), mid+1, R, l, r, k);
push_up(root);
}
LL Query(int root, int L, int R, int l, int r)
{
LL res = 0;
if(l<=L&&R<=r)
{
return tree[root];
}
push_down(root,L,R);
int mid = (L + R) >> 1;
if(l <= mid) res = (res + Query(ls(root), L, mid, l, r)) % mod;
if(r > mid) res = (res + Query(rs(root), mid+1, R, l, r)) % mod;
return res;
}
int main()
{
scanf("%d",&n);
F(i,1,n)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
int m = unique(b+1,b+n+1) - b - 1;
F(i,1,n)
{
a[i] = lower_bound(b+1,b+m+1,a[i]) - b;
}
F(i,1,n)
{
last[i]=ap[a[i]];
ap[a[i]]=i;
}
build(1,1,n);
F(r,1,n)
{
f[r] = (f[r-1] + r - last[r]) % mod;
res1 = (res1 + f[r]) % mod;
g[r] = (g[r-1] + 2 * Query(1,1,n,last[r]+1,r)) % mod;
res2 = (res2 + g[r]) % mod;
Update(1,1,n,last[r]+1,r,1);
}
printf("%lld",(res1 + res2) % mod);
return 0;
}