4 幸运数字

Rain Sure同学定义了幸运数字——如果一个正整数n是幸运数字，那么当且仅当n和(n+1)/2都是素数。

现在给定q次查询：

第i次询问给定两个正整数li,ri，请你求出在区间[li,ri]中有多少个数字是幸运数字。

输入格式

第一行一个正整数q。

后面q行，每行两个正整数li,ri

1≤q≤105

1≤li≤ri≤105

输出格式

对于每次询问，输出答案，每个答案单独占据一行。

测试样例一

1
3 7

2

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int prime[N],cnt;
int s[N];
bool st[N];
void get_prime(int n){for(int i=2;i<=n;i++){if(!st[i]){prime[cnt++]=i;}for(int j=0;prime[j]<=n/i;j++){st[prime[j]*i]=true;if(i%prime[j]==0)break;}}
}int main()
{get_prime(N-1);for(int i=2;i>q;while(q--){int l,r;scanf("%d%d",&l,&r);printf("%d\n",s[r]-s[l-1]);}return 0;
}

5 增加硬币

在一个袋子里装着A枚金币，B枚银币，C枚铜币

你需要将袋子里任意一种硬币变成至少100枚，你可以不断进行如下操作：

从袋子里随机选择一枚硬币，将其拿出袋子，然后将与这枚硬币相同的两枚硬币放入袋子中。

请你求出最少操作次数的期望值。

输入格式

输入一行，包括三个整数，分别代表A,B,C

0≤A,B,C≤99

A+B+C≥1

输出格式

输出最少操作次数的期望值。

当你输出的答案与标准答案的误差不超过10−6时，认为你的答案是正确的。

测试样例一

99 99 99

1.000000000

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 110;
double f[N][N][N];
int d = 0;double dp(int a, int b, int c) {if (f[a][b][c] >= 0)return f[a][b][c];f[a][b][c] = 0;if (a >= 100 || b >= 100 || c >= 100)return f[a][b][c];int sum = a + b + c;f[a][b][c] += (dp(a + 1, b, c) + 1) * (1.0 * a) / sum;f[a][b][c] += (dp(a, b + 1, c) + 1) * (1.0 * b) / sum;f[a][b][c] += (dp(a, b, c + 1) + 1) * (1.0 * c) / sum;return f[a][b][c];
}
int main()
{int a, b, c;scanf("%d%d%d", &a, &b, &c);memset(f, -1, sizeof f);printf("%.9lf", dp(a, b, c));return 0;
}

6 日落大道

给定一个n行m列的网格a，其中ai,j一定是这些字符中的一个S, G, ., #, a, ⋯, z。

其中#代表障碍物，你不可以走到这里，a ⋯ z代表不同种类的传送门。

Rain Sure同学一开始位于S处，他想要去G处，每次移动他可以进行下面两种操作中的一种：

• 移动到上下左右相邻中的一个格子，要求这个格子不能出界，不能是障碍物
• 进行传送，假如当前所在的位置是一个小写字母，他可以传送到任意一个是同样字母的位置。

请你求出Rain Sure同学从S移动到G所花费的最短时间。

如果不能到达，请输出-1。

输入格式

第一行两个正整数，分别代表n和m。

下面n行，每行m个字符，代表网格a。

1≤n,m≤2000

ai,j一定是S, G, ., #, a, ⋯, z中的一个。

保证只有一个位置是S，只有一个位置是G。

输出格式

请输出Rain Sure同学从S移动到G的最短时间，如果不能到达则输出-1。

测试样例一

2 5
S.b.b
a.a.G

4

7 ICPC保定站

Rain Sure同学来保定参加2077年的ICPC保定站了，这场比赛一共有n道题目，将会持续T分钟。

凭借他的超能力，Rain Sure同学可以预测到他可以花ai分钟来AC掉第i个题目。

所以，他将会从这n道题目中选择一些题目来做，当然也有可能全都做(因为AK最腻害了)，但是要保证花费的总时间不超过T分钟。

请你求出他能够在做题上花费的最长时间。

输入格式

第一行包括两个正整数，分别为n和T。

第二行有n个正整数，分别代表AC这道题需要花费的时间。

1≤n≤40

1≤T≤109

1≤ai≤109

输出格式

请输出Rain Sure同学能在做题上花费的最长时间。

测试样例一

5 17
2 3 5 7 11

17

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 50;
typedef pair PII;
int n, t, k;
int w[N];
LL weights[1 << 24], cnt = 0;
LL res;void dfs1(int u, LL s) {if (u == k) {weights[cnt++] = s;return;}dfs1(u + 1, s);if (s + w[u] <= t)dfs1(u + 1, s + w[u]);
}void dfs2(int u, LL s) {if (u == n) {int l = 0, r = cnt - 1;while (l < r) {int mid = l + r + 1 >> 1;if (weights[mid] <= (LL)t - s)l = mid;else r = mid - 1;}if (weights[l] + s <= t)res = max(res, weights[l] + s);return;}dfs2(u + 1, s);if (w[u] + s <= t)dfs2(u + 1, s + w[u]);
}int main()
{scanf("%d%d", &n, &t);for (int i = 0; i < n; i++)scanf("%d", &w[i]);sort(w, w + n);reverse(w, w + n);k = n / 2;dfs1(0, 0);sort(weights, weights + cnt);cnt = unique(weights, weights + cnt) - weights;dfs2(k, 0);cout << res;return 0;
}

8 染色问题

Arbalest给了Rain Suren个小方格。

并且其中有m个小方格的颜色是蓝色的，分别为a1,a2,a3,⋯,am，其余均为白色。

Arbalest让Rain Sure任意选择一个正整数k.

Rain Sure同学之后可以进行如下操作，选定一个长度为k的连续小方格(其中不许出现蓝色)，将他们全部染成红色。

Arbalest让Rain Sure把这n个小方格中白色的小方格全部变成红色。

请你帮助Rain Sure同学决定正整数k，并求出最少需要的操作次数。

输入格式

第一行包括两个整数，分别代表n和m。

第二行m个正整数a1,a2,⋯,am，其中ai代表第i个蓝色小方格的位置。

1≤n≤109

0≤m≤2×105

1≤ai≤n

保证ai各不相同

全部输入均为整数。

输出格式

请你输出最少需要的操作次数

测试样例一

5 2
1 3

3

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int n,m;
int s[N],w[N],cnt;
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
int main()
{scanf("%d%d",&n,&m);if(m==0){cout<<1;return 0;}if(n==m){cout<<0;return 0;}for(int i=1;i<=m;i++)scanf("%d",&w[i]);sort(w+1,w+m+1);w[0]=0;for(int i=1;i<=m;i++){int d = w[i]-w[i-1]-1;if(d>0)s[cnt++]=d;}int d = n-w[m];if(d>0)s[cnt++]=d;sort(s,s+cnt);int lst=s[0];int res=1;for(int i=1;i

4 3
1 2 1 3
1 3 1

2

#include 
using namespace std;
typedef long long LL;
const int N = 1010;
typedef pair PII;
int n, m;
int a[N], b[N];
int f[N][N];int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);for (int i = 1; i <= m; i++)scanf("%d", &b[i]);memset(f, 0x3f, sizeof f);for(int i=0;i<=n;i++)f[i][0]=i;for(int j=1;j<=m;j++)f[0][j]=j;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);}}cout << f[n][m];return 0;
}

3 4
1 2 3
2 1 3
2 2 3
1 2 3
2 2 3

0
1
2

#include 
#include 
#include 
#include using namespace std;const int N = 300010;int n, m;
int a[N], tr[N];int lowbit(int x)
{return x & -x;
}void add(int x, int v)
{for (int i = x; i <= n; i += lowbit(i)) tr[i] ^= v;
}int query(int x)
{int res = 0;for (int i = x; i; i -= lowbit(i)) res ^= tr[i];return res;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);for (int i = 1; i <= n; i++) add(i, a[i]);while (m--){int k, x, y;scanf("%d%d%d", &k, &x, &y);if (k == 2) printf("%d\n", query(y) ^ query(x - 1));else add(x, y);}return 0;
}

4
2 1
2 2
5 1
1 3

1

#include 
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
struct stu {LL a, b, c;
}st[N];LL resa;
int n;
bool cmp(stu s1, stu s2) {return s1.c > s2.c;
}
int main()
{scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &st[i].a, &st[i].b);resa += st[i].a;st[i].c = st[i].a * 2 + st[i].b;}sort(st, st + n, cmp);int res = 0;for (int i = 0; i < n; i++) {if (resa < 0)break;resa -= st[i].c;res++;}cout << res;return 0;
}