2022-03-21
https://codeforces.com/contest/1654/problem/C
//给你n堆蛋糕,问你是否存在一个蛋糕均分(奇数上下取整),切n-1刀得到这n堆蛋糕
//做法:dfs将数一直分开即可,遇到出现过的就不往下搜索,同时数字的数量减一
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
map<ll, int> mp;
bool dfs(long long x) {
if (mp[x]) {mp[x]--; return true;}//如果a数组存在x(能切),--(切割成功)并返回true
if (x == 1) return false;//a数组不存在1了,此时蛋糕重1无法切割 返回false
if (!dfs(x/2)) return false;//一半切不动了
if (!dfs(x-x/2)) return false;//另一半切不动了
return true;
}
int main() {
int t, n;
scanf("%d", &t);
while (t --) {
scanf("%d", &n);
mp.clear();
ll sum = 0;
for (int i = 0, x; i < n; i++) {
scanf("%d", &x);
mp[x]++;
sum += x;
}
puts(dfs(sum) ? "YES" : "NO");
}
}
https://codeforces.com/contest/1654/problem/B
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 2e5 + 10;
map<char, int> mp;
int as[N];
string s;
int t;
int main()
{
cin >> t;
while(t --)
{
cin >> s;
mp.clear();
for (int i = 0; i < s.size(); i ++)
{
mp[s[i]] ++;
as[i] = mp[s[i]];
}
int p;
for (int i = 0; i < s.size(); i ++)
{
if(as[i] - mp[s[i]] == 0)//当前位置的字母和该字母总数量相等 ----- 后面不会出现
{
p = i;
break;
}
}
for (int i = p; i < s.size(); i ++)
printf("%c", s[i]);
puts("");
}
return 0;
}
2022-03-25
B. https://ac.nowcoder.com/acm/contest/11223#question
假设有一个>2的数列不满足经重新排列后长度为2的区间之和不为0,即必然存在一个数x,使得数列无论如何排列,都存在...-x x -x...
,要否定这种情况,则至少得存在一个数z可以阻断这两个相反数...-x -x z x x...
此时也可以证明,若存在其他相反数如-c c ,-v v,-z z也可以分别再这个阻断的两边,则结论为:若数列中只存在两种数,且为相反数,即不存在第三个数用于阻断,则输出NO
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int N = 5e5 + 10;
int q[N];
int main()
{
int n;
scanf("%d", &n);
set<int> s;
for (int i = 0; i < n; i ++)
{
scanf("%d", &q[i]);
if(q[i] == 0)
{
puts("NO");
return 0;
}
s.insert(q[i]);
}
auto a = s.begin(), b = a ++;
if(s.size() == 2 && *a == -*b) puts("NO");
else puts("YES");
return 0;
}
C. map、map计数小技巧、二分、双指针
比如合适数对这道题
https://www.acwing.com/file_system/file/content/whole/index/content/4348273/
一般是枚举i或者j当中的某一个,比如枚举右端点(i)(定量),快速统计有多个满足条件的左端点(j)(变量),j < i, i - j <= k + 1
==> **i - 1 >= j >= i - k - 1**
那么就是在这个区间上找满足str[i] == str[j]
的数对
做法
开一个map数组,map<string, int> mp;
mp表示在【i - k - 1, i - 1】这个区间上有多少个str出现;
1. 枚举到i时,需要前[1, i - 1]区间上, 每出现一个str[i],,mp[str[i]] ++; [1, i - k - 2] 上 mp[str[i]] –;
2.此时问str[i] 在 [i - k - 1, i - 1] 区间上出现了多少次,就是mp[str[i]] ;
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int N = 1e5 + 10;
string str[N];
map <string, int > mp;
long long ans;
int main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> str[i];
for (int i = 1; i <= n; i ++ )
{
if(i - k - 2 >= 1) mp[str[i - k - 2]] --;
ans += mp[str[i]];
mp[str[i]] ++;
}
printf("%lld", ans);
return 0;
}
D. 《图(树)的存储》
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int d[N][3];
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
int main()
{
int n;
cin >> n;
memset(h, -1, sizeof h);
for (int i = 2; i <= n; i ++)
{
int b, c;
cin >> b >> c;
add (i, b, c), add(b, i, c);
}
for (int i = 1; i <= n; i ++)
for (int j = h[i]; j != -1; j = ne[j])
if(w[j] == 1) d[i][1] ++;
else if(w[j] == 2) d[i][2] ++;
for (int i = 1; i <= n; i ++)
for (int j = h[i]; j != -1; j = ne[j])
if(w[j] == 1) d[i][2] += d[e[j]][1] - 1;
for (int i = 1; i <= n; i ++) printf("%d\n", 1 + d[i][1] + d[i][2]);
return 0;
}