T1
题目描述
Gnaw 刚刚学习在数字逻辑中学到了格雷码，它的定义是这样的，对于二进制数 \(A\)，它对应的格雷码为 \(G = A \operatorname{xor} (A >> 1)\)，格雷码有个很有趣的性质是相邻二进制数对应的格雷码只有一位不同。
现在以 \(01?\) 的方式给出一个长为的二进制数 \(m\)，\(?\) 表示这个位置上可以填 \(0\) 或 \(1\). 现在给出 \(n\) 位分别对应的分数，当二进制 \(m\) 对应的格雷码在该位上为 \(1\) 是可以得到对应的分数。
输入格式
第一行一个二进制数串，包含 \(0, 1, ?\)，长为 \(n\)。
第二行 \(n\) 个数，表示对应位的分数 (分数小于 \(1000\)，大于 \(0\))。
输出格式
一个整数，表示可能的二进制数能得到的最大分数。
输入样例1
00?0
1 2 4 8
输出样例1
12
输入样例2
????
1 2 4 8
输出样例2
15
样例1解释、
\(0010\) 对应格雷码为 \(0010 \operatorname{xor} 001 = 0011\)，故得到 \(12\) 分。
数据规模
对于 \(30\%\) 数据，\(1 \leq n \leq 20\)。
对于 \(50\%\) 数据，\(1 \leq n \leq 2000\)。
对于 \(100\%\) 数据，\(1 \leq n \leq 200000\)。
完整代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 9;
int a[N], g[N], w[N], sum[N], n, ans = 0;
char ch[N];
signed main(){
freopen("gray.in", "r", stdin);
freopen("gray.out", "w", stdout);
scanf("%s", ch);
n = strlen(ch);
for(int i = 1; i <= n; i++)
if(ch[i - 1] == '1' || ch[i - 1] == '0')
a[i] = ch[i - 1] - '0';
else
a[i] = 2;
g[1] = a[1];
for(int i = 2; i <= n; i++)
if(a[i - 1] == 2 || a[i] == 2)
g[i] = 2;
else
g[i] = a[i] ^ a[i - 1];
for(int i = 1; i <= n; i++){
scanf("%lld", &w[i]);
sum[i] = sum[i - 1] + w[i];
}
sum[n + 1] = sum[n];
int l = 1, r = 1;
while(l <= n){
if(a[l] == 2){
r = l;
while(a[r] == 2)
r++;
r--;
if((a[l - 1] == a[r + 1] && (r - l + 1) % 2 == 1) || (a[l - 1] != a[r + 1] && (r - l + 1) % 2 == 0))
ans += sum[r + 1] - sum[l - 1];
else {
int id = 0, maxn = 0;
for(int i = l; i <= r + 1; i++){
if(sum[r + 1] - sum[l - 1] - (sum[i] - sum[i - 1]) > maxn){
maxn = sum[r + 1] - sum[l - 1] - (sum[i] - sum[i - 1]);
id = i;
}
}
g[id] = 0;
ans += maxn;
}
l = r;
}
l++;
}
for(int i = 1; i <= n; i++)
if(g[i] != 2)
ans += g[i] * w[i];
printf("%lld", ans);
return 0;
}
T2
题目描述
Miss D 是学财会的高材生，她有次扔给了 Gnaw \(N\) 个数，让 Gnaw 统计第 \(l\) 到第 \(r\) 个数中最小的数是多少。
Miss D 会有很多次询问哟~
输入格式
一个整数 \(n\) 表示有 \(n\) 个数据。
之后一行有 \(n\) 个数字，表示需要处理的 \(n\) 个数(\(\leq 10^9\))。
下一行一个数字 \(q\)。
之后又 \(q\) 行每行两个整数 \(l, r(1 \leq l \leq r \leq n)\)。
输出格式
\(q\) 行每行一个数字，表示从第 \(l\) 到 \(r\) 个数中最小的数是多少。
输入样例
5
3 2 1 4 3
3
1 3
2 4
4 5
输出样例
1
1
3
数据规模
对于 \(50\%\) 数据，\(1 \leq n \leq 10000, 1 \leq q \leq 1000\)。
对于 \(100\%\) 数据，\(1 \leq n \leq 100000, 1 \leq q \leq 10000\)。
完整代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9;
int t[N << 2], n, q;
void build(int id, int L, int R){
if(L == R){
scanf("%lld", &t[id]);
return;
}
int mid = (L + R) >> 1;
build(id << 1, L, mid);
build(id << 1 | 1, mid + 1, R);
t[id] = min(t[id << 1], t[id << 1 | 1]);
}
int query(int id, int L, int R, int qL, int qR){
if(L == qL && R == qR)
return t[id];
int mid = (L + R) >> 1;
if(qR <= mid)
return query(id << 1, L, mid, qL, qR);
else if(qL > mid)
return query(id << 1 | 1, mid + 1, R, qL, qR);
else
return min(query(id << 1, L, mid, qL, mid), query(id << 1 | 1, mid + 1, R, mid + 1, qR));
}
signed main(){
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
scanf("%d", &n);
build(1, 1, n);
scanf("%lld", &q);
for(int i = 1; i <= q; i++){
int L, R;
scanf("%lld%lld", &L, &R);
printf("%lld\n", query(1, 1, n, L, R));
}
return 0;
}
T3
题目描述
Miss D 和 gnaw 出去玩的时候，发现一个很奇怪的旅馆，宾馆老板特别喜欢数字 \(4\) 和 \(7\)，如果一个房间里住 \(4\) 或 \(7\) 个人，他就会很开心，不然他甚至不想让这个房间里住人。现在告诉你每个房间住的人数（\(7\) 人以内），将一个原在 \(i\) 号房间的人移动到 \(j\) 房间的代价是 \(\operatorname{abs}(i - j)\)，要想能满足老板的要求，花费的代价是多少？
输入格式
第一行一个数 \(n\)，表示房间数。
第二行 \(n\) 个数，表示每个房间原先住着的人数。
输出格式
一个数，表示按照老板要求最小的花费。
如果不能按要求分配，输出 \(-1\)。
输入样例
7
1 0 7 0 0 0 3
输出样例
6
数据规模
对于 \(50\%\) 数据，\(1 \leq n \leq 10^3\)。
对于 \(100\%\) 数据，\(1 \leq n \leq 10^5\)。
完整代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9, inf = 1e15;
int dp[N][15], a[N];
bool check(int t){
if(t == 0 || t == 4 || t == 7)
return true;
return false;
}
int n, ans = inf;
signed main(){
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
scanf("%lld", &n);
memset(dp, 0x3f, sizeof(dp));
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
dp[0][7] = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j <= 14; j++)
for(int k = 0; k <= 14; k++)
if(check(a[i + 1] - j + k))
dp[i + 1][k] = min(dp[i][j] + abs(k - 7), dp[i + 1][k]);
for(int i = 0; i <= 14; i++)
if(check(a[n] - i + 7))
ans = min(ans, dp[n - 1][i]);
if(ans == inf)
printf("-1");
else
printf("%lld", ans);
return 0;
}
T4
题目描述
Gnaw 给 Miss D 准备了一个长为 \(n\) 的礼物，还让 \(m\) 个朋友来帮他完成这个礼物，每个人开始是站在位置 \(p\)，最多可以装扮连续的长为 \(x\) 的部分，一个人可以不参与，一旦参与，他装扮的部分一定包含他一开始站的位置。每个人装扮长为 \(1\) 的部分能让整个礼物增加 \(y\) 的美丽度，gnaw 想让整个礼物的美丽值最高，会是多少?
输入格式
第一行两个整数 \(n, m\)，表示礼物长度和朋友数。
接下来 \(n\) 行，每行 \(3\) 个整数，分别为一个人最多装扮长度，单位美丽值和初始位置。
输出格式
一个整数，表示整个礼物最大的美丽值。
输入样例
8 4
3 2 2
3 2 3
3 3 5
1 1 7
输出样例
17
样例解释
1 号朋友装扮 \([1, 2]\)。
2 号朋友装扮 \([3, 4]\)。
3 号朋友装扮 \([5, 7]\)。
4 号朋友没有参与装饰。
数据规模
对于 \(30\%\) 数据，\(1 \leq n \leq 100, 1 \leq m \leq 100, 1 \leq y \leq 10000\)。
对于 \(100\%\) 数据，\(1 \leq n \leq 100, 1 \leq m \leq 16000, 1 \leq y \leq 10000\)。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 109, M = 16009;
int dp[N][M];
struct D{
int a, b, c;
} data[N];
bool cmp(D x, D y){
return x.c < y.c;
}
int q[M], tmp[M], n, m, start, rear;
int main(){
freopen("gift.in","r",stdin);
freopen("gift.out","w",stdout);
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; i++)
scanf("%d%d%d", &data[i].a, &data[i].b, &data[i].c);
sort(data + 1, data + n + 1, cmp);
for(int i = 1; i <= n; i++){
start = 0;
rear = 0;
for(int j = 0; j <= m; j++){
dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i][j]);
if(j + data[i].a >= data[i].c && j < data[i].c){
while(start < rear && q[rear - 1] <= dp[i - 1][j] - data[i].b * j)
rear--;
q[rear] = dp[i - 1][j] - data[i].b * j;
tmp[rear] = j;
rear++;
}
while(start < rear && ((tmp[start] + data[i].a < j) || (tmp[start] >= data[i].c)))
start++;
if(j >= data[i].c && data[i].c + data[i].a > j)
dp[i][j] = max(dp[i][j], q[start] + data[i].b * j);
}
}
printf("%d\n", dp[n][m]);
return 0;
}