1.数圈圈
十六进制是一种基数为 16 1616 的计数系统，是一种逢 16 1616 进 1 11 的进位制。
通常用数字 0、1、2、3、4、5、6、7、8、9 和字母 A、B、C、D、E、F 表示，其中: A ∼ F A∼FA∼F 表示 10∼15，这些称作十六进制数字。
观察这些数字的图案，我们可以发现，有些数字上面包含圈圈，具体来说：
数字 0,4,6,9,A,D 中包含一个圈。
数字8,B 中包含两个圈。
数字1,2,3,5,7,C,E,F 中不含圈。
现在，给定一个十进制整数 n，请你将其转化为十六进制表示，并数一数其十六进制表示中一共含有多少个圈圈。
输入格式
一个整数 n。
输出格式
一个整数，表示整数n 的十六进制表示包含的圈圈总数。
数据范围
前三个测试点满足 0≤n≤1000≤n≤100,
所有测试点满足 0≤n≤2×10^90≤n≤2×109。
输入样例1：
11
输出样例1：
2
输入样例2：
14
输出样例2：
0
题解
进制转换，没什么好说的
源代码
#include<iostream> using namespace std; int res; int n; int main() { cin >> n; while (n) { int t = n % 16; n = n / 16; if (t == 0 || t == 4 || t == 6 || t == 9 || t == 10 || t == 0xd) res++; else if (t == 8 || t == 0xb) res += 2; } cout << res; }
2.农田灌溉
输入格式
输出格式
每组数据输出一行答案。
数据范围
输入样例：
3
5 1
3
3 3
1 2 3
4 1
1
输出样例：
3
1
4
题解
#include<iostream> using namespace std; int n, k; int x[205]; int main() { int T; cin >> T; while (T--) { int res = 1; cin >> n >> k; for (int i = 1; i <= k; i++) cin >> x[i]; x[0] = 1; x[k + 1] = n; for (int i = 1; i < k; i++) res = max(res, (x[i + 1] - x[i]) / 2 + 1); res=max(res,x[1]); res=max(res,n-x[k]+1); cout << res<<endl; } return 0; }
3.选取数对
输入样例1：
5 2 1
1 2 3 4 5
输出样例1：
9
输入样例2：
7 1 3
2 10 7 18 5 33 0
输出样例2：
61
题解
源代码
#include<iostream> #include<cstring> using namespace std; int n, m, k; const int N = 5005; long long a[N]; long long s[N]; long long f[N][N];//最右右到i，选j个段 int main() { cin >> n >> m >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; memset(f, -0x3f3f3f3f3f3f3f3f, sizeof f); f[0][0] = 0; for(int i=0;i<=n;i++) f[i][0]=0; for (int i = m; i <= n; i++) { f[i][1] = max(f[i - m + 1][0] + s[i] - s[i - m], f[i - 1][1]); } for(int i=0;i<=n;i++){ for(int j=1;j<=k;j++){ if (i-m>=0) f[i][j]=max(f[i-m][j-1]+s[i]-s[i-m],f[i-1][j]); } } /* for(int i=0;i<=n;i++){ for(int j=0;j<=k;j++) if (f[i][j]<0) cout<<"-1 "; else cout<<f[i][j]<<" "; cout<<endl; }*/ cout<<f[n][k]<<endl; }
![[计蒜客] ACM-ICPC 2018 南京赛区网络预赛 | 部分题解 | 线段树 + 线性筛 + 最短路（上）](https://ucc.alicdn.com/pic/developer-ecology/d3c2fdd70f4d439380a044791e251bd3.png?x-oss-process=image/resize,h_160,m_lfit)