比赛链接: https://www.luogu.com.cn/contest/123979#description
A - Phone List
难度 ⭐
解题思路
一道比较裸的trie树的题; 但是我在题解中发现了一个很有意思的做法, 就是通过把字符串进行排序, 如果存在a是b的前缀, 那个a和b一定紧挨着;
神秘代码
//正常做法
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, idx;
int tr[N][10], h[N];
void ins(string s) {
int p = 0;
for (int i = 0; i < s.size(); i++) {
int u = s[i] - '0';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
}
h[p]++;
}
bool find(string s) {
int p = 0;
for (int i = 0; i < s.size()-1; i++) {
int u = s[i] - '0';
p = tr[p][u];
if (h[p]) return true;
}
return false;
}
void solve() {
memset(tr, 0, sizeof tr);
memset(h, 0, sizeof h);
idx = 0;
cin >> n;
vector<string> v;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
v.push_back(s);
ins(s);
}
for (auto t : v) {
if (find(t)) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
return;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
//技巧做法
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, idx;
void solve() {
cin >> n;
vector<string> v;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
v.push_back(s);
}
sort(v.begin(),v.end());
for(int i=1;i<v.size();i++){
string a=v[i-1],b=v[i];
int len=a.size();
if(b.substr(0,len)==a){
cout<<"NO"<<endl;
return;
}
}
cout<<"YES"<<endl;
return ;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B - Physics Problem
难度 ⭐⭐
解题思路
这个题如果能看懂题目给的提示就很好做了, 题目里说任意两个状态之间一定存在间接或直接的转换关系, 意思就是该图是一个存在环的连通图; 题目的输入相当于给了图中所有的直接关系, 一共有m个, 因为是连通图, 所以除了这m个外其他的都是间接关系, 而点和点之间的关系一个有C(n,2)个, 也就是在n个点中任取2个, 然后减去m就是正确答案;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int N = 1e6 + 10;
int n, m;
signed main() {
IOS;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
}
cout << n * (n - 1) / 2 - m;
return 0;
}
C - 英语1（eng1）- 英语作文
难度 ⭐
解题思路
用map把所有单词的含金量存起来; 把作文以空格分隔开可以用stringstream, 具体操作见代码; 记得剔除分隔符和不区分大小写;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int N = 1e6 + 10;
int n, m, p, res;
map<string, int> mp;
signed main() {
IOS;
cin >> n >> p;
for (int i = 1; i <= n; i++) {
string s;
int a;
cin >> s >> a;
mp[s] = a;
}
string s = "";
string t;
while (getline(cin, t)) s += t;
stringstream ss(s);
while (ss >> t) {
bool f = false;
string str = "";
for (int i = 0; i < t.size(); i++) {
if (t[i] == '.' || t[i] == ',' || t[i] == '?' || t[i] == '!') {
res = (res + mp[str]) % p;
str = "";
}
else str += t[i];
}
res = (res + mp[str]) % p;
}
cout << res;
return 0;
}
D - 游园安排
难度 ⭐⭐
解题思路
本质还是找最长上升子序列的线性dp, 注意本题不区分大小写;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int N = 1e6 + 10;
int n, m, p, maxn;
string dp[N];
string res[N];
vector<string> v;
signed main() {
IOS;
string s;
string t;
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] >= 'A' && s[i] <= 'Z') {
v.push_back(t);
t = s[i];
}
else t += s[i];
}
v.push_back(t);
int len = 0;
for (int i = 0; i < v.size(); i++) {
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (dp[mid] < v[i]) {
l = mid;
}
else r = mid - 1;
}
dp[r + 1] = v[i];
res[r + 1] = res[r] + v[i];
len = max(len, r + 1);
}
cout << res[len];
return 0;
}
E - 数正方形
难度 ⭐⭐
解题思路
又是一道思维题, 先算正着的子正方形, 很容易得知是(n - i) * (n - i), i是子正方形的边长; 本题主要是计算斜着是子正方形, 为了防止重复计算, 我们要保证该子正方形是大正方形才有的, 也就是说该子正方形的四个顶点都要在大正方形的四条边上, 在纸上多画几个会找到规律: 边长为n的正方形的边上除了两个顶点外有n-1个点, 这n-1个点都可以作为子正方形的一个顶点; 所以对于一个边长为n的正方形, 他包含了(1+(n-1))个子正方形, 也就是n个;
注意本题的n是点数, 边长是n-1;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, res;
signed main() {
cin >> n;
for (int i = 1; i < n; i++) {
res = (res + i * (n - i) * (n - i)%mod) % mod;
}
cout << res;
return 0;
}
F - 自适应 PVZ
难度 ⭐⭐⭐
解题思路
一道区间贪心的题目; 因为我们要把尽可能多的不冲突的区间相连, 所以可以把所有僵尸的出现时间段按右节点从小到大排序, 这样可以让序列尽可能的紧凑; 有m个豌豆射手我们就可以设置m个平行的序列, 并且受到线性dp的启发, 我们可以把序列的最后一个右节点用来代表整个序列; 在连接时, 对于一个时间段(左节点为l, 右节点为r), 我们可以在现有的所有序列中找到小于l的最大右节点R, 然后把这个时间段接到该序列后面, 这样就保证了序列的紧凑性; 因为要插入后排序, 所以我们可以用set来存所有序列的末尾节点; 如果所有序列的末尾节点都大于该时间段的右节点, 这时候如果还能看序列就新开一个序列, 否则就只能让过去;
这里还有一个小插曲, set的lower_bound函数只能用来找第一个大于等于给定值的数, 而我们的需要是找最后一个小于等于给定值的数, 找了很多资料发现不能通过修改比较器或者调整顺序来做到; 所以我只好用upper_bound函数找到第一个大于给定值的数, 然后用prev函数取它的前一个数的迭代器, 这个迭代器指的数就是最后一个小于等于给定值的数, 如果upper_bound返回的迭代器是begin()所有序列的末尾节点都大于该时间段的右节点; 搜了好长时间最后还是找的newbing才给我说明白...人工智能改变生活啊...
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10, mod = 1e9 + 7;
int n, m;
PII f[N];
multiset<int> s;
bool cmp(PII a, PII b) {
return a.second < b.second;
}
signed main() {
IOS;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
f[i] = { a,b };
}
sort(f + 1, f + 1 + n, cmp);
int num = 1, res = 0;
s.insert(f[1].second);
for (int i = 2; i <= n; i++) {
int a = f[i].first, b = f[i].second;
auto t = s.upper_bound(a);
if(t==s.begin()){
if (num < m) {
num++;
s.insert(b);
}
else res++;
}
else {
t = prev(t);
s.erase(t);
s.insert(b);
}
}
cout << res;
return 0;
}
I - 柯基棋
难度 ⭐
解题思路
博弈论, A先下; 如果n为奇数, A可以先下正中间, 并且之后的每一步都根据B下的位置在其中心对称的位置下, 这样下去A必胜; 如果n为偶数就反过来了, A成了被模仿的一方, 这样就是B必胜;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
int n, m;
signed main(){
int t;
cin>>t;
while(t--){
int n,a,b;
cin>>n>>a>>b;
if(n%2==1) cout<<"A won"<<endl;
else cout<<"B won"<<endl;
}
}