A. R

链接：https://ac.nowcoder.com/acm/contest/23479/A
来源：牛客网

题目描述

小红拿到了一个长度为 nn 的字符串，该字符串仅由大写字母组成。

小红很喜欢红色（用'R'字母表示），但她非常讨厌紫色（用'P'字母表示）。
她想取一个连续子串，该子串包含至少 kk 个'R'字符，且不能包含'P'字符。
你能告诉她有多少合法的方案可以取到吗？
注：只要连续子串的起始位置或终止位置不同，我们就认为是两个不同的方案。

输入描述:

第一行输入两个正整数 nn 和 kk ，用空格隔开。

输入一行字符串，该字符串保证仅包含大写字母（'A'到'Z'）。
数据范围：
1≤n≤2000001≤n≤200000
1≤k≤201≤k≤20

输出描述:

取一个连续子串，包含至少 k 个'R'字符、且不包含'P'字符的方案数。

示例1

输入

复制

13 3
RRRPBRRRDBRPR

输出

复制

10

说明

共有 10 个合法的子串选择方式。假设下标是从 0 到 12 ，那么 10 个合法串分别是：



s[0,2]s[0,2] = "RRR"
s[4,7]s[4,7] = "BRRR"
s[4,8]s[4,8] = "BRRRD"

s[4,9]s[4,9] = "BRRRDB"
s[4,10]s[4,10] = "BRRRDBR"

s[5,7]s[5,7] = "RRR"
s[5,8]s[5,8] = "RRRD"
s[5,9]s[5,9] = "RRRDB"

s[5,10]s[5,10] = "RRRDBR"
s[6,10]s[6,10] = "RRDBR"这些串均含有不小于 3 个字符 'R'，且不包含字符 'P'

和前面一场一个题很像，首先处理出所有不包含P的区间，然后枚举右端点，二分找满足条件的最靠右的左端点（可以证明答案具有单调性）然后剩下部分都可以作为左端点，计算贡献即可。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
#define ll long long 
int n, k;
char s[200006];
int sum[200005] = { 0 };
vector<pair<int, int> > v;
int main() {
	cin >> n >> k;
	scanf("%s", s + 1);
	int lst = 0;
	s[n + 1] = 'P';
	for(int i = 1; i <= n + 1; i++) {
		if(s[i] == 'P') {
			if(lst + 1 <= i - 1 && i - 1 - lst - 1 + 1 >= k) v.push_back(make_pair(lst + 1, i - 1));
			lst = i;
		}
	}
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1];
		if(s[i] == 'R') sum[i]++;
	}
	for(auto x : v) {
		int L = x.fi, R = x.se;
		for(int i = L; i <= R; i++) {
			int l = 1, r = i - L + 1, mid;
			while(l < r) {
				mid = (l + r) >> 1;
				if(sum[i] - sum[i - mid] >= k) {//注意要取等
					r = mid;
				} else l = mid + 1;
			}
			if(sum[i] - sum[i - l] == k) {
				ans += 1ll * (i - l + 1) - L + 1;
			}
 		}
	}
	cout << ans;
	return 0;
}

B. 进制

链接：https://ac.nowcoder.com/acm/contest/23479/B
来源：牛客网

题目描述

小红拿到了一个长度为 nn 的数字串 ss（只有 '0' ~ '9' 这十种字符），她有 qq 次以下两种操作：

第一种： 输入1 x y，修改第 x 个字符为 y ，即令sx=ysx=y
第二种： 输出 2 x y ，代表查询区间 [x,y]，该区间子串所能表示的某进制的最小值（进制必须合法，且必须是二进制到十进制之间，可以包含前导零），对 1000000007 取模。
例如若查询的子串为 "47"，其能表示的最小值是八进制代表的"47"，其数值为39，因此输出39。如果用十进制表示，则数值47，比39大。 例如若查询的子串为 "10000"，其能表示的最小值是二进制代表的"10000"，其数值为16，因此输出16。

输入描述:

第一行输入两个正整数 nn 和 qq ，用空格隔开。分别代表初始字符串和操作次数。
第二行输入一个长度为 nn的字符串 ss。
接下来的 qq 行，每行输入 3 个整数 op x yop x y，代表一次操作。
数据范围：
1≤n,q≤1051≤n,q≤105
opop 为 1 或者 2 。
若 opop 为 1，那么1≤x≤n1≤x≤n  ， 0≤y≤90≤y≤9

若 opop 为 2，那么1≤x≤y≤n1≤x≤y≤n  

输出描述:

对于每次 op=2op=2 的操作，输出该子串查询的合法进制最小值。由于该数过大，请对 1000000007 取模。

看到单点修改区间查询很容易想到线段树。可以在线段树的每个节点上维护2到10进制的这一段的和。注意，对于每个进制p，每个位置i的值x并非这个数本身，而是\(x\times p^{n - i}\)，即对于原串而言是从右到左由低到高。例如对于串12321，以4进制为例，第一个位置的值是81，第二个位置的值是54，那么[1, 2]的区间和是81+54=135。同时还要维护区间的对于每个位置数字的最值，比如对于串12321，[1, 4]的最值为3。这样对于每个询问，先找到区间的最值mx，mx+1就是需要使用的进制，这时再查询区间的对应这个进制的和。因为查询区间右端点r不一定等于n，因此还需要除以\(base^{n - r}\)，由于是在模意义下的除法，需要用到逆元。还需要注意，可能有这样的问题，例如对于串4567，如果是在2、3进制下实际上是没有意义的，因此对于a[pos] >= base的位置pos直接以0代替值即可。具体细节见代码。

#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define int long long
#define fi first
#define se second
using namespace std;
int n, q;
long long a[100006];
char s[100005];
struct SegmentTree {
	int l, r;
	long long dat[11];
	long long mx;
} t[100005 * 4];
ll fpow(ll a, ll b) {
	ll ans = 1;
	for(; b; b >>= 1) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}
void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if(l == r) {
		t[p].mx = a[l];
		for(int i = 2; i <= 10; i++) {
			if(i > a[l]) t[p].dat[i] = a[l] * fpow(1ll * i, n - l) % mod;//从右到左由低到高
			else t[p].dat[i] = 0ll;
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(2 * p, l, mid);
	build(2 * p + 1, mid + 1, r);
	t[p].mx = max(t[2 * p].mx, t[2 * p + 1].mx);
	for(int i = 2; i <= 10; i++) {
		t[p].dat[i] = (t[2 * p].dat[i] + t[2 * p + 1].dat[i]) % mod;
	}
}
ll ask_mx(int p, int l, int r, int L, int R) {
	if(t[p].l >= L && t[p].r <= R) {
		return t[p].mx;
	}
	int mid = (l + r) >> 1;
	ll ans = -1;
	if(L <= mid) ans = ask_mx(2 * p, l, mid, L, R);
	if(R > mid) ans = max(ans, ask_mx(2 * p + 1, mid + 1, r, L, R));
	return ans;
}
void modify(int p, int l, int r, int pos, ll x) {
	if(t[p].l == t[p].r) {
		t[p].mx = x;
		a[l] = x;
		for(int i = 2; i <= 10; i++) {
			if(i > a[l]) t[p].dat[i] = a[l] * fpow(1ll * i, n - l) % mod;//从右到左由低到高
			else t[p].dat[i] = 0ll;
		}
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) modify(2 * p, l, mid, pos, x);
	else modify(2 * p + 1, mid + 1, r, pos, x);
	t[p].mx = max(t[2 * p].mx, t[2 * p + 1].mx);
	for(int i = 2; i <= 10; i++) {
		t[p].dat[i] = (t[2 * p].dat[i] + t[2 * p + 1].dat[i]) % mod;
	}
}
ll ask_sum(int id, int p, int l, int r, int L, int R) {
	if(t[p].l >= L && t[p].r <= R) {
		return t[p].dat[id];
	}
	int mid = (l + r) >> 1;
	ll ans = 0;
	if(L <= mid) ans = ask_sum(id, 2 * p, l, mid, L, R);
	if(R > mid) ans = (ans + ask_sum(id, 2 * p + 1, mid + 1, r, L, R)) % mod;
	return ans;
}
signed main() {
	cin >> n >> q;
	scanf("%s", s + 1);
	for(int i = 1; i <= n; i++) {
		a[i] = s[i] - '0';
	}
	build(1, 1, n);
	while(q--) {
		int op;
		ll x, y;
		scanf("%d%lld%lld", &op, &x, &y);
		if(op == 1) {
			modify(1, 1, n, x, y);
		} else {
			ll mx = ask_mx(1, 1, n, x, y);
			//cout << mx << endl;
			mx++;
			ll ans = ask_sum(mx, 1, 1, n, x, y);
			//ans /= mx ** 
			ans = ans * fpow(fpow(mx, n - y), mod - 2) % mod;
			printf("%lld\n", ans);
		}
	}
}

C. 蓝彗星

链接：https://ac.nowcoder.com/acm/contest/23479/C
来源：牛客网

题目描述

你相信天上会出现蓝色的彗星吗？

小红是一个天文学爱好者。她最喜欢的业余活动就是天体观测。
这天夜里，星汉灿烂。小红拉上了小梦前往了教学楼的天台，组装好了天文望远镜。
根据预测，有两种不同颜色的彗星：红彗星和蓝彗星。每颗彗星会在某一时间段出现 tt 秒然后消失。
小红想知道，自己总共有多少秒，能看到蓝彗星且看不到红彗星？

ps：不用考虑昼夜更替等真实场景。我们假设小红所在的为架空世界，夜晚有无限长。

输入描述:

第一行输入两个正整数 nn 和 tt ，用空格隔开。分别代表彗星的数量、每个彗星的持续时间。
第二行输入一个长度为 nn 的，只有两种字符'B'和'R'组成的字符串。用来表示每颗彗星的颜色。字符'B'代表蓝色，字符'R'代表红色。
第三行输入 nn 个正整数 aiai ，代表每颗彗星的开始时刻。
数据范围：
1≤n,t,ai≤1000001≤n,t,ai≤100000

输出描述:

能看到蓝彗星且看不到红彗星的总秒数。    

区间覆盖判断，使用差分维护即可。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
#define ll long long 
int n, t, a[100005];
string s;
int d1[200005], d2[200005];
int main() {
	cin >> n >> t;
	cin >> s;
	s = " " + s;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	memset(d1, 0, sizeof(d1));
	memset(d2, 0, sizeof(d2));
	for(int i = 1; i <= n; i++) {
		if(s[i] == 'B') {
			d1[a[i]]++;
			d1[a[i] + t]--;
		} else {
			d2[a[i]]++;
			d2[a[i] + t]--;
		}
	}
	int ans = 0;
	for(int i = 1; i <= 200003; i++) {
		d1[i] += d1[i - 1];
		d2[i] += d2[i - 1];
		//cout << i << " " << d1[i] << " " << d2[i] << endl;
		if(d1[i] && d2[i] == 0) ans++;
	}
	cout << ans;
}

D. 雪色光晕

链接：https://ac.nowcoder.com/acm/contest/23479/D
来源：牛客网

题目描述

今年的雪来得格外的早。雪把大地染成一片橙色。

小红正在雪地中奔跑。雪地可以看成是一个二维平面，小红的初始坐标是 (x0,y0)(x0,y0)，她每秒有个方向向量 (xi,yi)(xi,yi)，会沿着该方向直线奔跑1秒（例如，第一秒之后，小红的坐标就变成了 (x0+x1,y0+y1)(x0+x1,y0+y1)。小果站在坐标 (x,y)(x,y)处原地不动。小红想知道，在跑步过程中，自己和小果的最短距离是多少？

输入描述:

第一行是一个正整数 nn ，代表小红奔跑的总时间。
第二行是四个整数 x0x0、 y0y0、xx 和 yy ，用空格隔开。用来表示小红的初始坐标和小果的坐标。

接下来的nn行，每行输入两个整数 xixi 和 yiyi ，用来表示小红每秒的方向向量坐标。
数据范围：
1≤n≤2000001≤n≤200000
−109≤x,y,xi,yi≤109−109≤x,y,xi,yi≤109

输出描述:

小红离小果最近的距离。如果你的答案和正确答案的相对误差不超过 10−710−7，则认为答案正确。

示例1

输入

复制

1
1 1 1 2
2 0

输出

复制

1.0

说明

小红在初始的位置上和小果的距离最近，为1.0

示例2

输入

复制

2
0 0 1 1
1 0
1 1

输出

复制

0.70710678

说明

小红和小果的初始距离是22
第一次从(0,0)到(1,0)，最近的距离在(1,0)处取到，是1.0。
第二次从(1,0)到(2,1)，最近的距离在(1.5,0.5)处取到，是22≈0.7071067822≈0.70710678
所以最小值是0.70710678

示例3

输入

复制

1
-10 0 1 1
20 0

输出

复制

1.0

实际上就是求n次点到线段的距离。直接抄kuangbin计算几何板子就能过～

int main() {
	ll n, x0, y0, x, y;
	cin >> n;
	cin >> x0 >> y0 >> x >> y;
	double ans = 1e18;
	ans = min(ans, f(x0, y0, x, y));
	for(int i = 1; i <= n; i++) {
		ll xi, yi;
		cin >> xi >> yi;
		Point a(x0, y0);
		Point b(x0 + xi, y0 + yi);
		Line line(a, b);
		Point p(x, y);
		ans = min(ans, line.dispointtoseg(p));
		x0 += xi;
		y0 += yi;
	}
	cout << fixed << setprecision(9) << ans;
}

E. 真假签到题

链接：https://ac.nowcoder.com/acm/contest/23479/E
来源：牛客网

题目描述

作为对萌新《友好》的寒假集训营，小红当然要送给大家一道签到题！

小红拿到了一份代码：

long long f(long long x){
    if(x==1)return 1;
    return f(x/2)+f(x/2+x%2);
}

给定一个正整数 xx ，她希望你能输出 f(x)f(x) 的值，你能帮帮她么？

输入描述:

一个正整数 xx 。
数据范围： 1≤x≤10181≤x≤1018

输出描述:

f(x)f(x) 的值。

示例1

输入

复制

1

输出

复制

1

说明

当 x=1x=1 时，函数将直接返回 1。

直接输出x。刚睡醒以为手速题还wa了两发，气坏了

F. 小红的记谱法

链接：https://ac.nowcoder.com/acm/contest/23479/F
来源：牛客网

题目描述

小红很喜欢音乐。她发现简谱有 2 种记谱的方法：

第一种是用 1234567 分别表示 do re me fa so la si

第二种是用 CDEFGAB 分别表示 do re me fa so la si

例如著名的《小星星》的表示方式，如果用第一种为 11556654433221 ，如果用第二种则是 CCGGAAGFFEEDDC 。

如果高了 8 度，那么对于第一种方式，可以采用在数字头顶加个点来表示。本题为了表示方便，则在数字后面加上一个 '*' 表示该数字为高八度。

同理，后面加了 x 个 '*' 代表高了 x 个八度。例如 2** 代表比普通的 2(re) 高了 16 度。

如果低了 8 度，那么对于第一种方式，可以采用在数字脚下加个点来表示。本题为了表示方便，则在数字后面加上一个 '.' 表示该数字为低八度。

同理，后面加了 x 个 '.' 代表低了 x 个八度。例如 2.. 代表比普通的 2(re) 低了 16 度。

举个例子，周杰伦的《夜曲》副歌部分的前两句用第一种简谱表示为：

6.7.11117.3366654511

而第二种记谱法和第一种不同的在于，尖括号’<‘代表后面所有的音比前面的音低 8 度。反尖括号'>'则代表后面所有的音比前面的音高 8 度。

例如，>>D 和第二种记谱法的 2** 是等价的，代表比 D 高了 16 度。

<<D 和第二种记谱法的 2.. 是等价的，代表比 D 低了 16 度。

那么《夜曲》的副歌部分的前两句用第二种简谱可以表示为：

<AB>CCCC<B>EEAAAGFGCC 

再例如，《opara2》是vitas著名的高音之作。其中一个片段（副歌前到第一句副歌）用两种记谱法分别可以表达如下：

3.7.6.127.127.13.7.6.1243236232323.32327.7.7.7.127.7*1**2**3**2**3**2**1**7*1**2**7*
<EBA>CD<B>CD<B>C<EBA>CDFEDEADEDED<E>EDED<BBBB>CD<B>>B>CDEDEDC<B>CD<B

转到副歌第一句：”7.712323**…………“这里时，由于7比7.高了2个8度，所以后面要接两个>，之后的1**到达了一个更高的音程，所以在B后面继续接一个>。

因此这部分应该记为">B>CDEDE…………"

请注意，第二种记谱法并不是唯一的，例如：

11.1..

转为第二种记谱法，可以记为：

C<C><<C>>

但也可以记为：

C<C<C

不过第一种记谱法一定是唯一表示的。

现在给出一段第二种记谱法的简谱，小红希望你能输出对应的第一种记谱法。

输入描述:

一行字符串, 为第二种记谱法的简谱。
字符串长度不超过1000。

输出描述:

一行字符串, 为第一种记谱法描述的简谱

示例1

输入

复制

<<<<<<<<ECA>>>>>>>>

输出

复制

3........1........6........

说明

音调的音域(度)上不封顶, 下不封底。输入中末尾的 '>' 也都是可以省略的，代表同一张谱的表示。

示例2

输入

复制

G>GFEEFEEFEFEDC<

输出

复制

55*4*3*3*4*3*3*4*3*4*3*2*1*

示例3

输入

复制

<G>GDEC>C<GEC>C<G>EDGB>C

输出

复制

5.52311*5311*53*2*5*7*1**

示例4

输入

复制

<EBA>CD<B>CD<B>C<EBA>CDFEDEADEDED<E>EDED<BBBB>CD<B>>B>CDEDEDC<B>CD<B

输出

复制

3.7.6.127.127.13.7.6.1243236232323.32327.7.7.7.127.7*1**2**3**2**3**2**1**7*1**2**7*

简单模拟，难点在于读懂又臭又长的题干～

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
#define ll long long 
map<char, char> m;
int main() {
	m['C'] = '1', m['D'] = '2', m['E'] = '3', m['F'] = '4', m['G'] = '5', m['A'] = '6', m['B'] = '7';
	string s, ans = "";
	cin >> s;
	int base = 0;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == '>') {
			base++;
		} else if(s[i] == '<') {
			base--;
		} else {
			ans += m[s[i]];
			for(int i = 1; i <= abs(base); i++) {
				if(base < 0) ans += '.';
				else if(base > 0) ans += '*';
			}
		}
	}
	cout << ans;
}

G. 子序列权值乘积

链接：https://ac.nowcoder.com/acm/contest/23479/G
来源：牛客网

题目描述

小红定义一个数组的权值为该数组的最大值乘以最小值。例如数组 [4,1,3] 的权值是 4*1=4。

小红拿到了一个数组。她想知道，这个数组的所有 非空****子序列 的权值的乘积是多少？由于该数过大，请对1000000007取模。

子序列的定理：对于一个数组，删除其中某些数之后（也可以不删）得到的数组。子序列中的数的相对顺序必须和原数组中的顺序相同。

例如：数组 [1,3,2] 的非空子序列有 [1] [3] [2] [1,3] [1,2] [3,2] [1,3,2] 共7个。

输入描述:

第一行输入一个正整数 nn ，代表数组的长度。
第二行输入 nn 个正整数 aiai ，代表小红拿到的数组。
数据范围：
1≤n≤2000001≤n≤200000
1≤ai≤1091≤ai≤109

输出描述:

数组所有子序列的权值的乘积。答案对1000000007取模。

示例1

输入

复制

2
2 3

输出

复制

216

说明

对于子序列 [2,3] ，其权值为 3 * 2 = 6。
对于子序列 [2] ，其权值为 2 * 2 = 4。
对于子序列 [3] ，其权值为 3 * 3 = 9。
因此所有非空子序列的权值乘积为： 6 * 4 * 9 = 216

示例2

输入

复制

4
4 1 4 3

输出

复制

757784222

首先注意到选的是自序列，因此顺序实际上没有关系，可以先排个序，然后考虑每个数作为最大值和最小值对答案的贡献。因为答案本身就是每个自序列最大值最小值之积的积，所以这里可以直接乘。

#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
using namespace std;
#define ll long long 
#define int long long
int n, a[200005], o[200005];
int b[200005];
void add(int x, int y) {
	for(; x <= 200000; x += (x & -x)) b[x] += y;
}
int ask(int x) {
	int ans = 0;
	for(; x; x -= (x & -x)) ans += b[x];
	return ans;
}
int f[200005];
ll fpow(ll a, ll b) {
	ll ans = 1;
	for(; b; b >>= 1) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}
signed main() {
	cin >> n;
	vector<int> v;
	f[0] = 1;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		f[i] = (f[i - 1] * 2) % (mod - 1);
	}
	sort(a + 1, a + n + 1);
	ll ans = 1;
	for(int i = 1; i <= n; i++) {
		ans = ans * fpow(a[i], f[i - 1] + f[n - i]) % mod;
	}
	cout << ans;
	return 0;
}

H. 真真真真真签到题

链接：https://ac.nowcoder.com/acm/contest/23479/H
来源：牛客网

题目描述

作为对萌新友好的寒假集训营，小红当然要送给大家一道签到题！

小红和紫被困在一个正方体的内部。紫先选择了一个位置，然后小红选择一个位置。紫希望离小红尽可能近，小红希望离紫尽可能远。两人都会选择最优策略。
已知她们最终的距离为 xx 。小红想知道正方体的体积是多少？

输入描述:

一个正整数 xx 。
数据范围： 1≤x≤1001≤x≤100

输出描述:

最终正方体的体积。如果你的答案和正解的相对误差不超过 10−410−4，则认为你的答案正确。

示例1

输入

复制

13

输出

复制

3382.5027771

说明

紫先选择站在正方体的中心，然后小红站在正方体的一个角上。可以证明这样一定是最优的。

初中几何题。实际上样例解释已经说出答案了。。

#include <bits/stdc++.h>
using namespace std;
int main() {
    double x;
    cin >> x;
    cout << fixed << setprecision(6) << pow(x * 2 / sqrt(3), 3);
}

I. 爆炸的符卡洋洋洒洒

链接：https://ac.nowcoder.com/acm/contest/23479/I
来源：牛客网

题目描述

小红正在研究如何把符卡组合出尽可能大威力的组合魔法。

小红共有 nn 种符卡可以选择，每种符卡最多只能选择一次，每个符卡的魔力消耗为 aiai，威力为 bibi。
如果将多个符卡进行组合，则可以发动一个组合魔法。组合魔法的魔力消耗为选择的符卡的魔力消耗的总和，其威力为选择的符卡的威力的总和。
小红必须保证最终符卡的魔力消耗总和为 kk 的倍数，否则小红将受到魔力反噬而发动魔法失败。
小红想知道，自己能发动的组合魔法最大的威力是多少？

输入描述:

第一行输入两个正整数 nn 和 kk ，用空格隔开。
接下来的 nn 行，每行输入两个正整数 aiai 和 bibi，用空格隔开。
数据范围：
1≤n,k≤10001≤n,k≤1000
1≤ai,bi≤1091≤ai,bi≤109

输出描述:

如果小红无论如何也组合不了能发动的魔法，则输出-1。
否则输出最大的威力值。

示例1

输入

复制

2 3
1 2
2 1

输出

复制

3

说明

两个符卡都选上，融合出的魔法消耗为3，是3的倍数。威力是3。

示例2

输入

复制

2 2
1 2
2 1

输出

复制

1

说明

选择第二个符卡，消耗为2，是2的倍数。威力是1。

示例3

输入

复制

3 4
1 2
5 3
1 4

输出

复制

-1

说明

显然，无论如何都组合不出消耗为4的倍数的魔法。

dp，设dp[i, j]为使用前i个能凑出j的消耗值（模k意义下）的最大威力。模k以后就可以写出n^2的dp了，转移方程见代码。注意发生转移的条件是前一个状态的威力不为0！同时不要忘记当前卡不选的话也要更新dp数组。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
#define ll long long 
ll n, k;
ll a[1005], b[1005];
ll dp[2005][2005];
int main() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		a[i] %= k;
	}
	ll ans = 0;
	for(ll i = 1; i <= n; i++) {
		dp[i][a[i]] = b[i];
		for(ll j = 0; j <= k - 1; j++) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			if(dp[i - 1][(j - a[i] + k) % k]) 
				dp[i][j] = max(dp[i][j], dp[i - 1][(j - a[i] + k) % k] + b[i]);
		}
		ans = max(ans, dp[i][0]);
	}
	if(ans) cout << ans;
	else cout << -1;
	return 0;
}
// 3 3
// 1 5 
// 2 5
// 2 7

J. 区间合数的最小公倍数

链接：https://ac.nowcoder.com/acm/contest/23479/J
来源：牛客网

题目描述

小红拿到了两个正整数 ll 和 rr 。
她想知道 [l,r][l,r] 区间所有合数的最小公倍数是多少？由于答案可能过大，请对1000000007取模。
合数的定义：因子的个数不小于3的正整数。例如：9的因子有1、3、9这三个，所以9是合数。

输入描述:

两个正整数 ll 和 rr ，用空格隔开。
数据范围：1≤l≤r≤300001≤l≤r≤30000

输出描述:

若区间 [l,r][l,r] 中没有任何合数，则输出-1。
否则输出区间 [l,r][l,r] 所有合数的最小公倍数，答案对1000000007取模。

示例1

输入

复制

2 3

输出

复制

-1

说明

区间 [2,3] 的两个数 2 和 3 都是素数，不是合数。

示例2

输入

复制

4 6

输出

复制

12

说明

区间[4,6]中有三个数：4、5、6，其中 5 是素数， 4 和 6 是合数，它们的最小公倍数是12。

示例3

输入

复制

25000 30000

输出

复制

187554966

直接硬求也可以（注意除法换成逆元），或者用LCM的性质：https://www.cnblogs.com/lipoicyclic/p/14387217.html

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define maxn 1e5
using namespace std;
long long x[10005], p[10005];
int n, sg[1000007], primes[1000007];
int cnt[1000007] = { 0 };
bool is[1000006] = { 0 }; 
int m=0; 
void getprimes(){
    sg[1]=0;
    for(int i=2;i<=maxn;i++){
        sg[i]=1;
    }
    for(int i=2;i<=maxn;i++){
        if(sg[i]==1) {sg[i]=1;primes[++m]=i; is[i] = 1;}
        for(int j=1;j<=m&&primes[j]*i<=maxn;j++){
            sg[primes[j]*i]=sg[i]+1;
            if(i%primes[j]==0)break;
        }
    }
}
ll fpow(ll a, ll b) {
	ll ans = 1;
	for(; b; b >>= 1) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}
int main()
{
	int l, r;

	cin >> l >> r;
	getprimes();
	for(int i = l; i <= r; i++) {
		if(is[i]) continue;
		int tmp = i;
		for(int j = 1; j <= m; j++) {
			if(primes[j] > tmp) break;
			if(tmp % primes[j] != 0) continue;
			int tot = 0;
			while(tmp % primes[j] == 0) tot++, tmp /= primes[j];
			cnt[primes[j]] = max(tot, cnt[primes[j]]);
		}
	}
	ll ans = 1;
	for(int i = 1; i <= m; i++) {
		 ans = ans * fpow(primes[i], cnt[primes[i]]) % mod;
	}
	if(ans != 1) cout << ans;
	else cout << -1;
	return 0;
}

K. 小红的真真假假签到题题

二进制下整体右移相当于乘2，为了保证1的个数不相同，再加上x即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main() {
	ll x;
	cin >> x;
	cout << (x << 32) + x;
	return 0;
}