打表过样例
题目描述
很不幸，你遇到了不负责任的出题人。
在某道试题里，共有 \(N\) 个测试点，组成了 \(k\) 个 Subtask，第 \(i\) 个 Subtask 包含 \(p_i\) 个测试点，第 \(j\) 个测试点的编号为 \(w_{i,j}\)。请注意，一个测试点可能属于多个 Subtask。
Subtask
每个 Subtask 包含多个测试点和一个分值，当且仅当通过全部这些测试点时，才能获得这个 Subtask 的分值。一道题目的得分为通过的所有 Subtask 分值之和。
这是一道输出仅有一个数的题目，编号为 \(i\) 的测试点，标准答案为 \(A_i\)。
很不幸，由于命题人不负责任，\(A_i\) 中出现了大量重复，让打表选手有了可乘之机。
现在，你通过某种手段获得了全部的数据，请问输出哪个数，可以得到最高的分数？最高的分数是多少？
如果有多个数均可得到最高的分数，你只需要任意给出一个。
输入格式
输入共 \(k+3\) 行。
输入的第一行为一个正整数 \(k\)。
接下来 \(k\) 行：
- 第 \(i\) 行的第一个数为 \(p_i\)，代表第 \(i\) 个 Subtask 包含的测试点数目。
- 接下来 \(p_i\) 个数，第 \(j\) 个代表测试点编号 \(w_{i,j}\)。
- 最后一个数为 \(S_i\)，代表这个 Subtask 的分值。
输入的第 \(k+2\) 行为一个正整数 \(N\)。
输入的第 \(k+3\) 行为 \(N\) 个非负整数，第 \(i\) 个代表 \(A_i\)。
输出格式
输出两行，每行一个整数。
第一行表示获得的最大分值。
第二行表示输出的数。
如果有多个数可以取到相同的最大分值，任意输出一个即可。
样例 #1
样例输入 #1
2
3 1 2 3 5
3 4 5 6 7
6
4 4 4 5 5 5
样例输出 #1
7
5
提示
数据规模与约定
- 对于 \(30\%\) 的测试数据，\(1 \le N \le 100\)，\(1 \le k,p_i \le 10\)，\(1 \le A_i \le 100\)。
- 对于 \(100\%\) 的测试数据，\(1 \le N \le 10^5\)，\(1 \le k,p_i \le 5000\)，\(1 \le w_{i,j} \le N\)，\(1 \le S_i \le 10^9\)，\(1 \leq A _ i \leq 10 ^ 9\)。
思路
这题没想到剪枝，打了个部分分暴力。
赛后看了方老师AK的代码，发现原来有个关键剪枝。
for(int i=1;i<=nk;i++)
{
ans=test[sub[i][0]];
get_score=true;
for(int len=sub[i].size(),j=1;j<len;j++)
{
if(ans != test[sub[i][j]])
{
get_score=false;
break;
}
}
if(get_score)
score[ans]+=sub_s[i];
}
一旦一个substack里面出现两种不同的答案，肯定不可能可以，直接排除掉，不参与后面的答案枚举，这样就能过。
异或构造题
题目描述
给定 \(n\) 个非负整数 \(a _ 1, a _ 2, \cdots, a _ n\)，你需要确定一个非负整数 \(x\)，使得 \(a _ 1 \oplus a _ 2 \oplus \cdots \oplus a _ n \oplus x\) 最小。
你需要计算 \(x\) 和 \(a _ 1 \oplus a _ 2 \oplus \cdots \oplus a _ n \oplus x\)。
其中 \(\oplus\) 代表异或，\(x \oplus y\) 在 C++ 中可表示为 x ^ y。
对于两个非负整数 \(x,y\)，它们的异或是指，将它们作为二进制数，对二进制表示中的每一位进行如下运算得到的结果：
- \(x\) 和 \(y\) 的这一位上不同时，结果的这一位为 \(1\)；
- \(x\) 和 \(y\) 的这一位上相同时，结果的这一位为 \(0\)。
例如：\(0\oplus 0=0\)，\(1\oplus 0=1\)，\(0\oplus 1=1\)，\(1\oplus 1=0\)。
输入格式
输入共两行。
第一行一个整数 \(n\)，代表序列 \(a\) 的长度。
第二行 \(n\) 个整数 \(a _ 1, a _ 2, \cdots, a _ n\)，代表序列 \(a\)。
输出格式
输出共一行两个整数 \(x\) 和 \(a _ 1 \oplus a _ 2 \oplus \cdots \oplus a _ n \oplus x\)。
样例 #1
样例输入 #1
2
1 2
样例输出 #1
3 0
样例 #2
样例输入 #2
2
7 7
样例输出 #2
0 0
提示
数据规模与约定
对于 \(100\%\) 的数据，\(1 \leq n \leq 10 ^ 6\)，\(0 \leq a _ i \leq 10 ^ {18}\)。
| 测试点 | \(n\) | \(a _ i\) | 特殊性质 |
|---|---|---|---|
| \(1\) | \(= 1\) | \(\leq 10 ^ 3\) | 无 |
| \(2\) | \(= 2\) | \(\leq 10 ^ 3\) | \(a _ 1 = a _ 2\) |
| \(3 \sim 4\) | \(= 2\) | \(\leq 10 ^ 3\) | 无 |
| \(5\) | \(\leq 10 ^ 3\) | \(= 0\) | 无 |
| \(6 \sim 8\) | \(\leq 10 ^ 3\) | \(\leq 10 ^ 3\) | 无 |
| \(9 \sim 11\) | \(\leq 10 ^ 6\) | \(\leq 10 ^ 3\) | 无 |
| \(12 \sim 13\) | \(\leq 10 ^ 6\) | \(\leq 1\) | 无 |
| \(14 \sim 20\) | \(\leq 10 ^ 6\) | \(\leq 10 ^ {18}\) | 无 |
思路
秒了。
但是没开 long long。
似乎是下意识觉得异或这种运算不会越界？
铅球杯
题目描述
蓝边铅球组织了“铅球杯”数据标注大赛。为了实现 Au 大满贯的宏大征途，LeAuingZ 报名参加了比赛。
蓝边铅球给出了 \(N\) 个 int 类型变量的名字及其值，并要求 LeAuingZ 对 \(k\) 句话进行数据标注。每句话由大小写英文字母、空格、半角逗号、半角句号和 {、} 组成。在 {} 之间的，为 \(N\) 个变量名中的一个，LeAuingZ 需要将每一句话中全部的 {变量名} 替换为变量的值并输出。
例如，有 \(a=3,b=4\)，对于句子 We know a is {a}, b is {b}.，替换后将得到 We know a is 3, b is 4.。
LeAuingZ 觉得这个任务很无聊，决定编写一个程序来快速获得 Au。
输入格式
输入共 \(N+k+1\) 行。
输入的第一行为两个整数 \(N,k\)。
接下来 \(N\) 行，每行一个小写英文字符串、一个整数，分别代表变量名和变量的值。
接下来 \(k\) 行，每行一个需要标注的句子。
输出格式
输出 \(k\) 行，每行一个标注好的句子。
样例 #1
样例输入 #1
5 2
abc 1
a 2
b 3
c 4
d 5
We have {a} apples.
We {d}onot have pencils.
样例输出 #1
We have 2 apples.
We 5onot have pencils.
提示
- 对于 \(20\%\) 的测试数据，\(k=1\)。
- 对于另外 \(30\%\) 的测试数据，\(1 \le N \le 26\)，变量名长度均为 \(1\)。
- 对于 \(100\%\) 的测试数据，\(1 \le N \le 5000\)，\(1 \le k \le 20\)。变量名仅含英文小写字母，变量名长度不超过 \(20\)，变量的值在 int 范围内，标注前句子长度不超过 \(5 \times 10^4\)，保证
{}成对合法出现。每句话由大小写英文字母、空格、半角逗号、半角句号和{、}组成。
思路
唯一难点就是读入。
我第一反应没想到 getline，导致 getchar() 的时候各种麻烦，整整改了半小时才改好，1400分的题变成了700分。。。
getchar JOKER方法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define LL long long
#define YES std::cout<<"YES"<<std::endl
#define Yes std::cout<<"Yes"<<std::endl
#define NO std::cout<<"NO"<<std::endl
#define No std::cout<<"No"<<std::endl
long long ceil_x(long long a, long long b)
{
if (a % b == 0)
return a / b;
else
return (a / b) + 1;
}
const long long mod = 1e9 + 7;
const int N = 310000;
const int M = 300;
int n, m;
std::map<std::string, int> tag;
char ch;
int t;
int main()
{
scanf("%d%d", &n, &m);
std::string s;
for (int i = 1; i <= n; i++)
{
std::cin >> s >> t;
tag[s] = t;
}
ch = getchar();
while (m--)
{
while (ch = getchar())
{
if (ch == '\n')//一开始是写.，然而不一定会以句号结束，还得是用'\n'稳妥
{
break;
}
if (ch == '{')
{
std::string temp = "";
while (scanf("%c", &ch) && ch != '}')
{
temp += ch;
}
printf("%d", tag[temp]);
continue;
}
printf("%c", ch);
}
printf("\n");
}
return 0;
}
getline FLS极致优雅
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#define ll long long
using namespace std;
map <string, string> cx;
bool replace;
int n, nk;
string ins, ans, tmp, s1, s2;
int main()
{
scanf("%d%d", &n, &nk);
for (int i = 1; i <= n; i++)
{
cin >> s1 >> s2;
cx[s1] = s2;
}
getline(cin, ins);
for (int ls, i = 1; i <= nk; i++)
{
getline(cin, ins);
ans = "";
ls = ins.size();
replace = false;
for (int j = 0; j < ls; j++)
{
switch (ins[j])
{
case '{':
replace = true;
tmp = "";
break;
case '}':
replace = false;
ans += cx[tmp];
break;
default:
if (replace)
tmp += ins[j];
else
ans += ins[j];
}
}
cout << ans << endl;
}
return 0;
}