题目戳这里
A.A Serial Killer
题目描述似乎很恶心，结合样例和样例解释猜测的题意
使用C++11的auto可以来一手骚操作
#include <bits/stdc++.h>
using namespace std;
int n;
string s[];
map <string, int> p;
int main() {
cin >> s[] >> s[];
p[s[]] = p[s[]] = ;
cin >> n;
cout << s[] << " " <<s[] << endl;
while(n --) {
cin >> s[] >> s[];
p[s[]] ++, p[s[]] ++;
for(auto iter : p)
if(iter.second == ) cout << iter.first << " ";
puts("");
}
return ;
}其实等价于这样写
#include <bits/stdc++.h>
using namespace std;
int n;
string s[];
map <string, int> p;
int main() {
cin >> s[] >> s[];
p[s[]] = p[s[]] = ;
cin >> n;
cout << s[] << " " <<s[] << endl;
while(n --) {
cin >> s[] >> s[];
p[s[]] ++, p[s[]] ++;
for(map <string, int>::iterator iter = p.begin();iter != p.end();iter ++)
if(iter -> second == ) cout << iter -> first << " ";
puts("");
}
return ;
}B.Sherlock and his girlfriend
很蠢的一题，质数标1，合数标2就好了
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j;i <= k;i ++)
#define rev(i, j, k) for(int i = j;i >= k;i --)
using namespace std;
typedef long long ll;
const int maxn = ;
int n, a[maxn];
int main() {
ios::sync_with_stdio(false);
cin >> n;
if(n < ) puts("");
else puts("");
for(int i = ;i <= n + ;i ++)
if(a[i] != ) {
a[i] = ;
for(int j = i << ;j <= n + ;j += i)
a[j] = ;
}
for(int i = ;i <= n + ;i ++)
printf("%d ", a[i]);
return ;
}C.Molly's Chemicals
有那么一点意思的题目
求有多少段连续子段和为k的非负power
显然k为2的话，大概能2^0 - 2^50左右吧
所以直接枚举 k^p 即可
偷懒套个map，复杂度O(n(logn)^2)
注意:
1.非负power，包括1
2. |k| = 1 特判，否则死循环
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j;i <= k;i ++)
#define rev(i, j, k) for(int i = j;i >= k;i --)
using namespace std;
typedef long long ll;
int n, t;
ll k, s[];
map <ll, int> p;
int main() {
ios::sync_with_stdio(false);
int x;
cin >> n >> t;
rep(i, , n) cin >> x, s[i] = s[i - ] + x;
for(ll j = ;abs(j) <= 100000000000000ll;j *= t) {
p.clear(), p[] = ;
rep(i, , n) {
k += p[s[i] - j];
p[s[i]] ++;
}
if(t == || (t == - && j == -)) break;
}
cout << k;
return ;
}D.The Door Problem
应该注意到each door is controlled by exactly two switches
所以显然对于一开始锁上的门，只能选择一个开关
一开始打开的门，可以选择都不选或者都选
于是我们可以想到2-sat来解决
实际上2-sat也的确可以解决
但是我们注意到这个2-sat的特殊性
每组中的两个选择在某种程度上是等价的
而我们平时做的 Ai 与 Ai’ 是不等价的
两个选择等价意味着连的边已经是无向边
即若有Ai -> Aj，则必有Aj -> Ai
这样就不需要再tarjan
直接并查集就可以解决了
#include <cstdio>
const int maxn = ;
int n, m, f[maxn << ], a[][maxn];
bool op[maxn];
int find_(int x) {
if(f[x] != x) return f[x] = find_(f[x]);
return x;
}
void union_(int x, int y) {
x = find_(x), y = find_(y);
if(x != y) f[x] = y;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = ;i <= n;i ++) scanf("%d", &op[i]);
for(int k, j, i = ;i <= m;i ++) {
scanf("%d", &j);
while(j --) {
scanf("%d", &k);
if(a[][k]) a[][k] = i;
else a[][k] = i;
}
}
for(int i = m << ;i;i --) f[i] = i;
for(int i = ;i <= n;i ++)
if(op[i]) union_(a[][i], a[][i]), union_(a[][i] + m, a[][i] + m);
else union_(a[][i], a[][i] + m), union_(a[][i] + m, a[][i]);
for(int i = ;i <= m;i ++)
if(find_(i) == find_(i + m)) {
puts("NO");
return ;
}
puts("YES");
return ;
}E.The Holmes Children
手动计算发现 f 函数为欧拉函数
gcd(x, y) = 1
x + y = n
=> gcd(x, x + y) = 1 即 gcd(x, n) = 1
g(n) = n ，剩下部分很好解决
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod_ = 1e9 + ;
ll f(ll x) {
ll ret = x;
for(ll i = ;i * i <= x;i ++)
if(x % i == ) {
ret /= i, ret *= (i - );
while(x % i == ) x /= i;
}
if(x != ) ret /= x, ret *= (x - );
return ret;
}
int main(){
ll n, k;
cin >> n >> k;
k = (k + ) >> ;
for(int i = ;i <= k;i ++) {
n = f(n);
if(n == ) break;
}
cout << n % mod_;
return ;
}