2023/11/9
Codeforces Round 908 (Div. 2) 补题
A. Secret Sport
简单签到，一个思路就是比赛结束总是在刚刚得出胜者的时候，所以最后一个人总是获胜的
B. Two Out of Three
签到
C. Anonymous Informant （补）
思路：逆推，因为每次左移的时候，选择的数总是会到最后一位，那么我们就可以看当前最后一位数是谁，就可以知道上一轮选了谁，那么当进入循环或者k次结束时，最后一位数都没有大于n，那么就是合法的。否则，就是不合法
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
map<int, int> mp;
vector<int> alls;
const int N = 201010;
int a[N];
int vis[N];
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
vis[i] = 0;
}
int pos = n;
vis[pos] = 1;
if (a[n] > n)
{
cout << "No\n";
return;
}
while (k--)
{
if (a[pos] > n)
{
cout << "No\n";
return;
}
vis[pos] = 1;
pos = (pos - a[pos] + n) % n;
if (pos == 0)
pos = n;
if (vis[pos])
{
cout << "Yes\n";
return;
}
}
cout << "Yes\n";
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
D - Neutral Tonality（补）
题意：让我们往只有的序列里面加数，使最后的LIS最小。
这个其实是自己写的，赛时被C卡了没时间。
思路：我们加数的时候就和原来的a数组里的数比较，对于一个a[i]我们让选a[i]是优于我们加进去的数就行，这样我们就可以让LIS最小，对于一个a[i],我们若在他前面降序加入大于等于a[i]的数，那么肯定是选a[i]更优的。因为这lis同等长度结尾更小，自然更优。 若遍历a[n]结束，b还没填完，说明有一部分数太小了，比a中任何一个数都小，那个自然加到末尾就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e5 + 10;
int a[N], b[N];
vector<int> alls;
void solve()
{
alls.clear();
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int j = 1; j <= m; j++)
cin >> b[j], alls.push_back(b[j]);
sort(alls.begin(), alls.end());
for (int i = 1; i <= n; i++)
{
int x = alls.size() - 1;
for (int j = x; j >= 0; j--)
{
if (alls[j] >= a[i])
{
cout << alls[j] << " ";
alls.pop_back();
}
else
break;
}
cout << a[i] << " ";
}
for (int j = alls.size() - 1; j >= 0; j--)
{
cout << alls[j] << " ";
}
cout << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
中午vp edu157（2/7）
Educational Codeforces Round 157 (Rated for Div. 2）补题
A - Treasure Chest
简单签到
B. Points and Minimum Distance
算总的距离，那么不走回头路是最好的，然后画图得总距离为相距最远得两个点，所以排序后x拿前n个，y拿后n个即可
C. Torn Lucky Ticket（补）
忘记这种（i,j）(j,i)算两种的计数怎么做了
思路：把每个字符串的长度和值都先用map存下，然后遍历累加即可。因为每个字符串的长度最多只有5，枚举分界线，把符合的数累加。一个分割，知道前后的长度和值，所以我们只需要这两个对上就行。mp开二维map<int,map<int,int>> mp;mp[len] [val] 来记录长度和总和
注意：string的size函数是unsigned long long ，-1要特别注意
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e5 + 10;
int a[N], b[N];
string s[N];
map<int, map<int, int>> mp;
int getint(string x)
{
int res = 0;
for (int j = 0; j < x.size(); j++)
{
res += x[j] - '0';
}
return res;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
int len = s[i].size();
s[i] = " " + s[i];
int res = 0;
for (int j = 1; j <= len; j++)
{
res += s[i][j] - '0';
}
mp[len][res]++;
// cerr << len << " " << res << endl;
}
// cerr << mp[1][1] << endl;
int ans = 0;
for (int i = 1; i <= n; i++)
{
int len = s[i].size();
for (int j = 1; j < len; j++)
{
// cerr << j << endl;
string str1 = s[i].substr(1, j);
string str2 = s[i].substr(j + 1);
// cerr << str1 << " TTTT " << getint(str1) << endl;
// cerr << str2.size() << endl;
ans += mp[(int)str2.size() - (int)str1.size()][getint(str2) - getint(str1)];
ans += mp[(int)str1.size() - (int)str2.size()][getint(str1) - getint(str2)];
}
}
cout << ans << endl;
}
signed main()
{
Acode;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
D. XOR Construction（待补）
赛时推公式，公式规律找的没问题，但是只能找到n为奇数的规律。后来看大佬的题解发现要用字典树。先去学！
字典树学习 板子
Trie树（字典树）
可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。
trie 的结构非常好懂，我们用son[u] [c]表示结点 u 的c字符指向的下一个结点编号，或着说是结点u代表的字符串后面添加一个字符c形成的字符串的结点。(26 的取值范围和字符集大小有关 )
有时需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。
const int N = 2e5 + 10;
int n, idx;
int son[N][27];
int cnt[N];
void insert(string s)
{
int p = 0;
for (int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
if (!son[p][u])
son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
int query(string s)
{
int p = 0;
for (int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
if (!son[p][u])
return 0;
p = son[p][u];
}
return cnt[p];
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
char ch;
string s;
cin >> ch;
cin >> s;
if (ch == 'I')
insert(s);
else
{
cout << query(s) << endl;
}
}
}