【题解】自创题目题解

解谜

结论题，若是$3|n$，则答案是$n/3$；否则答案是$n$
证明如下：
首先，对于一个点，最多被操作一次。因为操作两次等于没操作，操作三次等于操作一次。
其次，对于一个点，一开始是暗的状态，目标是把他变成亮的状态。那么一定是被改变了奇数次的状态。对于一个点，当这个点被改变了状态，一定是该点（下面称作为“我”），或者左边那个点（左一）或者右一被操作了。只有这三个点才可能改变我的状态。
所以对于我而言，想要最终亮的，要么被改变一次状态，要么被改变三次状态。
一种方案一定是对每个点都点一次，每个点都被改变三次状态，每个点都被点亮，答案是$n$
考虑减少操作次数，肯定是去考虑对于其中一个点，比如我而言，是否能实现只被改变一次状态。

就假设在我上操作一次，不操作左一右一，那么我就只被改变了一种状态。但是为了使得左一和右一同样能亮，因为左一和右一被认定是不能操作了，所以左二和右二也不能操作。
但是还得使得左二和右二点亮，所以一定得操作左三右三。
所以这种假设如果成立，那么操作的方案就必须是，我，左三，左六，左九……右三，右六……
考虑周期性，从我出发，左三过去和右三过去必须重合，所以这种假设对应的方案就是每隔两个点操作一次，能实现的前提是$3|n$，不然无法重合

Code：

#include 
using namespace std;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	char s1[100], s2[100];
//	for (int opt = 1; opt <= 20; ++opt){
//		sprintf(s1, "puzzle%d.in", opt);
//		sprintf(s2, "puzzle%d.out", opt);
//		freopen(s1, "r", stdin);
//		freopen(s2, "w", stdout);
	int n = read();
	printf("%d\n", n % 3 == 0 ? n / 3 : n);
//		fclose(stdin); fclose(stdout);
//	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

摩拉

这题是一个类斐波那契数列。
依题意$f[0]=1,f[1]=p,f[2]=p+1,f[3]=2p+1,f[4]=3p+\mathrm{2...}$
现我令$g[0]=1,g[1]=1,g[2]=2,g[3]=3,g[4]=\mathrm{5...}$
则$h[x]=f[x]-g[x],h[1]=p-1,h[2]=p-1，h[3]=2(p-1),h[4]=3(p-1)...$
得到$h[i]=g[i-1]\ast (p-1)$

因为$a,b<=20$,$g$数组可以预处理
对于一组$a,x,b$
$f[a]=x=h[a]+g[a]=g[a-1](p-1)+g[a]$
$f[b]=h[b]+g[b]=g[b-1](p-1)+g[b]$

联立得到$f[b]=\frac{g[b-1](x-g[a])}{g[a-1]}+g[b]$
注意到这边有一个分数，所以输出-1的情况，即不存在$p$使得$f[a]=x$的情况是这个分数的分母无法整除分子

Code：

#include 
#define LL long long
using namespace std;
LL g[100];

int main(){
	LL a, x, b;
	g[0] = g[1] = 1;
	for (int i = 2; i <= 20; ++i) g[i] = g[i - 1] + g[i - 2];
	while (scanf("%lld%lld%lld", &a, &x, &b) != EOF){
		if ((x - g[a]) % g[a - 1] != 0){
			puts("-1");
			continue;
		}
		cout << g[b] + g[b - 1] * (x - g[a]) / g[a - 1] << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

烟花

其实这道题很简单
如果想到把公差设计到状态里面去，难度就急剧下降了
令$d{p}_{i,j}$表示以$a_i$结尾，且公差为$j$的等差数列（数列的长度至少为2）有多少个
所以我们花$O(nm)$的时间枚举状态，再花$O(n)$的时间转移
$$d{p}_{i,j}+=d{p}_{k,j}+1(a_k+j=a_i)$$
这样我们就拿到了60分的好成绩
但是其实根本不必枚举公差是多少
对于一个公差$d$，若不存在$a_x,a_y$，使得$a_x+d=a_y$，这个公差是没有意义的，为了处理这个冗余，我们直接枚举两个数，由这两个数确定公差
$$d{p}_{i,a_i-a_j}+=d{p}_{j,a_i-a_j}+1$$
这样$O(n^2)$就解决了
如何统计答案呢，这里需要和$dp$数组一起更新
$$ans+=d{p}_{j,a_i-a_j}+1$$
最终输出$ans+n$，因为每个数单独一个也算

Code：

#include 
#define maxn 40010
#define maxm 1010
using namespace std;
const int qy = 19260817;
int n, a[maxn], dp[maxm][maxn], ans;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	int p = 20000;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j < i; ++j){
			(dp[i][a[i] - a[j] + p] += dp[j][a[i] - a[j] + p] + 1) %= qy;
			(ans += dp[j][a[i] - a[j] + p] + 1) %= qy;
		}
	printf("%d\n", (ans + n) % qy);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

若你困于无风之地

这道题目是一次操作是把几个区间依次翻转过来，要进行$k$次操作。
注意到$k<=10^9$，一般来说就是要考虑周期性问题了。

对于进行了一次操作后，每个数都会有一个具体的去处，令$nxt[i]$表示进行一次操作之后位置$i$上的数会到$nxt[i]$上
这个很好理解，不管某个位置上的数是什么，进行了一次操作后，位置3上的数会到位置6上比如；那么之后每次操作均会如此。
所以注意到$nm<=10^7$，可以做一遍预处理，模拟一次操作把$nxt$数组求出来
这样就可以$i-->nxt[i]$这样连边，用图论的观点看的话可以把这个看成一张图，而这张图一定是由几个环组成的。
对于每个环，环的大小就是循环节，就是周期。对于每个环独立处理，用$k$对循环节取模，然后就可以直接赋值了

Code：

#include
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}
int ans[100010];int nxt[100010];int l[110];int r[110];
int t[100010];bool in[100010];

int main(){
	int n,m,k;read(n);read(m);read(k);
	rep(i,1,m){read(l[i]);read(r[i]);}
	rep(i,1,n){
		int now=i;
		rep(j,1,m){
			if(l[j]<=now&&now<=r[j])now=l[j]+r[j]-now;
		}
		nxt[i]=now;
	}
	
	rep(i,1,n){
		if(in[i])continue;
		int now=i;int len=0;
		do{
			t[++len]=now;in[now]=1;now=nxt[now];
		}while(!in[now]);
		
		rep(j,1,len){int nop=(j+k-1)%len+1;ans[t[nop]]=t[j];}
	}
	rep(i,1,n)write(ans[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

神女

首先要考虑贪心，所有的-1是都要收入囊中的。
然后考虑-1都有的情况下，尽可能取多的树木。
对于$x,-1,y$
若是我想要把$x与y$都取到，必须满足$x+1<y$，即$x<y-1$
那么就可以推广了
令$cnt[i]$表示到$i$为止-1的个数
那么对于剩下的正整数$a[i]$，求$a[i]-cnt[i]$的最长上升子序列的长度就是能取得最多的树木
最后在加上-1的个数

最长上升子序列用$O(nlogn)$的二分+单调的求法

Code：

#include 
#define maxn 100010
using namespace std;
int m, d[maxn], len, ans;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	m = read();
	for (int i = 1; i <= m; ++i){
		int x = read();
		if (x == -1) ++ans;
		else{
			x -= ans;
			if (!len || x > d[len]) d[++len] = x;
			else{
				int l = 1, r = len, pos = 0;
				while (l <= r){
					int mid = (l + r) >> 1;
					if (d[mid] >= x) pos = mid, r = mid - 1; else l = mid + 1;
				}
				d[pos] = x;
			}
		}
	}
	printf("%d\n", ans + len);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

牛杂

每天只能买或者卖，一开始我们可能会去想做$DP$，但是行不太通，跟dp有关的思路我懒得写了。
这道题目是一个反悔贪心的模板题。

反悔贪心是我们口头形容的一种不成体系的算法，差不多可以算作是一种思想。
比如这一道题目，我们可以把之前出现过的价格都放到小根堆里面，对于当前第$i$天，价格是$a[i]$
然后把小根堆的根取出来，记为$x$，这个$x$就是之前最小的价格。
然后我们就贪心，用$x$买入股票，$a[i]$卖出股票，赚取一个差价。
之后一步操作很关键，先将$a[i]$放入小根堆，再把这个$x$变成$a[i]$也放入小根堆

如何理解这个操作呢，我举个例子
比如之前有个2
现在来了个5，那么我们肯定要赚取这个3的差价，然后把2变成5放回去，小根堆里面的数是{5,5}
然后如果又来了个7，我们将赚取2的差价，小根堆里的数是{5,7,7}，可以把这步理解为之前用5的价格卖出不划算了，我们反悔了，改而用7卖出
然后如果又来了个7，我们将再赚取2的差价，小根堆里的数是{7,7,7,7}，那么我们把这整个过程就看做是2,5买入，7,7卖出。只不过中途经历了一个2买入5卖出然后反悔的过程

Code:

#include 
#define maxn 500010
#define LL long long
using namespace std;
LL ans;
int n;
 
inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}
 
int main(){
    n = read();
    priority_queue <LL, vector<LL>, greater<LL> > q;
    for (int i = 1; i <= n; ++i){
        int x = read();
        q.push(x);
        if (x > q.top()) ans += x - q.top(), q.pop(), q.push(x);
    }
    printf("%lld\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

智慧

一开始我们可能会尝试去构造，然后去寻找规律
大致思路是根据规律确定答案的位数，然后逐位确定。但是我们可以用二分

发现一个规律，k进制下结尾有奇数个0，就表示这个数满足要求，就是能被$k$整除而不能被$k^2$整除；能被$k^3$整除，而不能被$k^4$整除……能被$k^{2n-1}$整除而不能被$k^{2n}$整除
所以就可以使用容斥了
对于我们二分的一个$mid$，计算$1mid$有几个可爱数
就是$\frac{mid}{k}-\frac{mid}{k^2}+\frac{mid}{k^3}-...$

Code：

#include  
#include  
#include  
#include  
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define inf 0x3f3f3f3f
#define P pair<int,int>
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("output/out.txt", "w", stdout)
using namespace std;
typedef unsigned u;
typedef unsigned long long ull;
typedef long double ld;
 
LL solve(LL n, int k) {
    LL tn = n;
    LL res = 0;
    for (; n/k>=1; n/=(k*k)) {
        LL l = 1, r = n/k;
        LL num = r-r/k;
        res += num;
    }
    return res;
}
LL n;
int k;
int main()
{
    cin >> n >> k;
    LL l = 1, r = 1e18;
    while (l < r-1) {
        LL m = (l+r) >> 1;
        if (solve(m, k) <= n-1) l = m;
        else r = m;
    }
    cout << r <<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

神里

这道题目的背景已以及解答在这里

大祓

这道题目的背景
这道题目也是一个反悔的贪心，先把背景题目搞懂之后，我把数列变成了二叉树问题
这边呢，是满二叉树，目标是变成二叉排序树。那么我们就进行一个中序遍历，遍历之后的数列就是转换成我一开始说的那个题目了。

炸弹

以样例为例，我们这样排列数字

枚举所有人最多不能超过$i$个炸弹，就把超过的部分买回来
然后我自己至少得拥有$i+1$个炸弹，所以如果不够的话，从下面取
可以用线段树维护炸弹，所以需要一开始离散化
我们从大到小枚举i，可以实现每次能从线段树里面删除炸弹，每次从线段树里统计最小的几个价格之和

Code：

#include 
#define maxn 100010
#define ls rt << 1
#define rs rt << 1 | 1
#define LL long long
using namespace std;
struct data{
	int cnt, id;
}v[maxn];
struct Seg{
	int l, r, cnt;
	LL sum;
}seg[maxn << 2];
struct node{
	int a, c;
}a[maxn];
vector <node> w[maxn];
int val[maxn], pos[maxn], n, m, p, point[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool cmp(data x, data y){
	return x.cnt > y.cnt;
}

bool cmp1(node x, node y){
	return x.a < y.a;
}

void pushup(int rt){
	seg[rt].cnt = seg[ls].cnt + seg[rs].cnt;
	seg[rt].sum = seg[ls].sum + seg[rs].sum;
}

void build(int rt, int l, int r){
	seg[rt].l = l, seg[rt].r = r;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(ls, l, mid), build(rs, mid + 1, r);
}

void update(int rt, int pos, int delta){
	if (seg[rt].l == seg[rt].r){
		seg[rt].cnt += delta, seg[rt].sum += val[pos] * delta;
		return;
	}
	if (seg[ls].r >= pos) update(ls, pos, delta);
	else update(rs, pos, delta);
	pushup(rt);
}

LL query(int rt, int x){
	if (seg[rt].l == seg[rt].r) return 1LL * x * val[seg[rt].l];
	if (seg[ls].cnt >= x) return query(ls, x);
	else return seg[ls].sum + query(rs, x - seg[ls].cnt);
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		a[i].a = read(), a[i].c = read();
		++v[a[i].c].cnt;
	}
	for (int i = 1; i <= n; ++i) v[i].id = i;
	sort(v + 1, v + 1 + n, cmp);
	for (int i = 1; i <= n; ++i) pos[v[i].id] = i;
	sort(a + 1, a + 1 + m, cmp1);
	for (int i = 1; i <= m; ++i){
		if (a[i].a != a[i - 1].a) ++p;
		int id = pos[a[i].c];
		w[id].push_back((node){a[i].a, p});
		a[i].c = p, val[p] = a[i].a;
	}
	build(1, 1, p);
	for (int i = 1; i <= m; ++i) update(1, a[i].c, 1);
	LL sum = 0, ans = 1e15, num = 0;
	for (int i = m; i; --i){
		for (int j = 1; j <= n; ++j)
			if (w[j].size() - point[j] > i){
				while (w[j].size() - point[j] > i) ++num, sum += w[j][point[j]].a, update(1, w[j][point[j]].c, -1), ++point[j];
			} else break;
		if (num <= i) ans = min(ans, sum + query(1, i + 1 - num));
		else ans = min(ans, sum);
	}
	printf("%lld\n", ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

千岩

1操作是区间修改
2操作是修改
3操作是单点查询
可以用主席树无脑过
但是我们可以有更加智慧的方法

如果没有2操作的话，这道题目就是裸题了，我们现在要解决2操作的问题
对于一个3询问$\text{(3 l r)}$，找到之前离我们最近的$\text{(2 l x)}$，在那个操作的时候给这个3询问对应的答案加一个减标记，在3询问的时候给3询问对应的答案加一个加标记
这样一来，标记都是给对应的答案加的，然后中间那一部分就是2操作之后新更改的，实现了查分

区间修改与单点查询用树状数组更为方便，线段树也可以
对于增加标记的事情，一个2操作可能会带有多个标记，可以用vector，但是我不习惯，用了链式前向星

Code：

#include 
#define maxn 200010
#define LL long long
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;
LL tree[maxn];
struct Edge{
    int to, x, y, next;
}edge[maxn << 1];
int num, head[maxn], n, m, Q, pos[maxn], cnt;
LL ans[maxn], sum[maxn];
struct Ques{
    int opt, l, r;
    LL delta;
}q[maxn];
 
inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}
 
void addedge(int u, int v, int y, int x){
    ++num;
    edge[num].to = v;
    edge[num].x = x;
    edge[num].y = y;
    edge[num].next = head[u];
    head[u] = num;
}
/* 
对于所有的3操作，定位到最近的一次跟3有关的2操作，在2操作的位置上进行一个减操作
定位到这个询问之前最晚的一次1/2操作，进行一个加操作 
 */
 
int lowbit(int x){ return x & -x; }
void add(int x, LL delta){ for (; x <= m; x += lowbit(x)) tree[x] += delta; }
LL query(int x){ LL sum = 0; for (; x; x -= lowbit(x)) sum += tree[x]; return sum; }
 
int main(){
    n = read(), m = read(), Q = read();
    int last = 0;
    for (int i = 1; i <= Q; ++i){
        q[i].opt = read();
        if (q[i].opt == 1){
        	q[i].l = read(), q[i].r = read(), q[i].delta = read();
        	last = i;
		}
        if (q[i].opt == 2){
            int x = read(), y = read();
            pos[x] = i, sum[x] = y;
            last = i;
        }
        if (q[i].opt == 3){
            q[i].l = read(), q[i].r = read();
            int p = pos[q[i].l];
            ++cnt;
            addedge(p, cnt, q[i].r, -1);
            addedge(last, cnt, q[i].r, 1);
            ans[cnt] = sum[q[i].l];
        }
    }
    for (int i = 1; i <= Q; ++i){
        if (q[i].opt == 1){
        	add(q[i].l, q[i].delta);
        	add(q[i].r + 1, -q[i].delta);
		}
        for (int j = head[i]; j; j = edge[j].next){
            ans[edge[j].to] += edge[j].x * query(edge[j].y);
        }
    }
    for (int i = 1; i <= cnt; ++i) printf("%lld\n", ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77