传送门 A. Cards 记录一下出现的个数就行。 Code #include bits/stdc++.h#define MP make_pair#define fi first#define se second#define sz(x) (int)(x).size()//#define Localusing namespace std;typedef long long ll;typedef pairint, in
传送门
A. Cards
记录一下出现的个数就行。
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
char s[N];
int cnt[26];
void run() {
cin >> s + 1;
int n = strlen(s + 1);
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= n; i++) {
cnt[s[i] - 'a']++;
}
int Min = min(cnt['o' - 'a'], cnt['e' - 'a']);
Min = min(Min, cnt['n' - 'a']);
for(int i = 1; i <= Min; i++) cout << 1 << ' ';
for(int i = 1; i <= cnt['z' - 'a']; i++) cout << 0 << ' ';
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
int n; while(cin >> n) run();
return 0;
}
B. Multiplication Table
题意：
存在一个序列\(a\)，现在给出一个矩阵\(M\),\(M_{ij}=a_i\cdot a_j\)。但现在序列和矩阵主对角线上面的元素遗失了。
现在要求\(a\)序列，数据保证有解。
思路：
- 容易发现，\(a_1\)确定后，后面的也就能依次确定了。
- 考虑怎么确定\(a_1\)，枚举显然不行，如果只是去猜测一个值检验，时间复杂度也不能承受。
- 容易发现\(a_1\cdot a_2,a_1\cdot a_3,a_2\cdot a_3\)的值我们都知道，那么就可以求出\(a_1^2\)，那么就可以直接得到序列了。
代码如下：
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e3 + 5;
int n;
int a[N][N];
void run() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
int ab = a[1][2], ac = a[1][3], bc = a[2][3];
ll a2 = 1ll * ab * ac / bc;
int a1 = sqrt(a2 + 0.5);
cout << a1 << ' ';
for(int i = 2; i <= n; i++) cout << a[1][i] / a1 << ' ';
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n) run();
return 0;
}
C. Substring Game in the Lesson
挺水的一个题，记录一下前面最小的就行。
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e5 + 5;
char s[N];
void First() {
cout << "Ann" << '\n';
}
void Second() {
cout << "Mike" << '\n';
}
void run() {
int n = strlen(s + 1);
int Min = 30;
for(int i = 1; i <= n; i++) {
if(Min >= s[i] - 'a') Second();
else {
First();
}
Min = min(Min, s[i] - 'a');
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> s + 1) run();
return 0;
}
D. Alex and Julian
题意：
给出一个集合\(B\)，对于集合中的每个\(b_i\)，将对所有的\(i,j\)满足\(|i-j|=b_i\)连边。
现在问最少去掉哪些数使得最终得到的为二分图。
思路：
感觉挺巧妙的，现在假设\(a,b,a<b\)这两个数发生了碰撞。
那么有\(xa=yb=t\cdot lcm(a,b)=t\cdot \frac{ab}{gcd(a,b)}\)。
那么就有：\(x=\frac{bt}{gcd(a,b)},y=\frac{at}{gcd(a,b)}\)。
因为\(t\)为固定的，所以分析下即可得到，要满足\(x+y\)不为奇数，\(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)}\)要同奇偶。
因为这里有个\(gcd(a,b)\)有点烦，我们现在考虑将\(a,b\)表示为乘积的形式：考虑\(a=2^ip,b=2^jq\)，这里\(p,q\)为奇数。
那么\(gcd(a,b)=2^{min(i,j)}gcd(p,q)\)，这里易知\(gcd(p,q)\)也为奇数，假设\(i<j\)，那么现在\(\frac{a}{gcd(a,b)}=\frac{p}{gcd(p,q)},\frac{b}{gcd(a,b)}=\frac{2^{j-i}q}{gcd(p,q)}\)。
那么答案马上就出来啦，可以发现当\(i=j\)时，奇数除以一个奇数一定也为一个奇数；否则，第一个式子为奇数，第二个式子分子为偶数，分母为奇数，整个式子一定为偶数，就不同奇偶了。
所以我们按照\(2\)的次幂进行划分，最后贪心就行了。
感觉还是挺巧妙的，将\(a,b\)换成\(2^i\)与另外一个数的乘积怎么想得到啊QAQ难道因为\(2\)比较特殊？
详见代码：
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n;
ll a[N], b[N];
void run() {
vector <ll> v[66];
for(int i = 1; i <= n; i++) {
cin >> a[i]; b[i] = a[i];
int cnt = 0;
while(a[i] % 2 == 0) {
++cnt; a[i] /= 2;
}
v[cnt].push_back(b[i]);
}
int Max = -1, p;
for(int i = 0; i <= 60; i++) {
if(sz(v[i]) > Max) {
Max = sz(v[i]);
p = i;
}
}
int ans = n - Max;
cout << ans << '\n';
for(int i = 0; i <= 60; i++) {
if(i == p) continue;
for(auto it : v[i]) cout << it << ' ';
}
if(ans) cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n) run() ;
return 0;
}
E. Tourism
题意：
给出一个无向图，每个点都有相应权值。现在从起点\(s\)出发，不同连续经过一条边两次，问最多可以获得多少权值。
思路：
- 容易发现，如果走到了类似于一条链上的东西，那就永远无法回头了QAQ。
- 所以考虑从度为\(1\)的点往里类似于拓扑排序那样来标记点，同时记录一下路径，用来处理特殊情况。
- 显然最后那些没有标记的点都要走，之后贪心考虑一条路径权值最大的走就行。
- 注意一下为一棵树的特殊情况，上述算法不能处理。
有一点细节，代码中我用了一个\(nxt\)数组来记录下一个位置，但是有一个问题，一个点的出度有多个点怎么办？
稍微思考一下就可以发现，这种情况不会发生，如果发生了，就成功到达目的地了~否则，就是在一条符合要求的链上面走。
另外注意走过的点权值记为0。
详见代码：
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n, m;
int w[N];
struct Edge{
int v, next;
}e[N << 1];
int head[N], tot;
void adde(int u, int v) {
e[tot].v = v; e[tot].next= head[u]; head[u] = tot++;
}
int d[N], nxt[N];
ll dis[N];
bool vis[N];
void dfs(int u) {
vis[u] = 1;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(!vis[v]) {
dis[v] = dis[u] + w[v];
dfs(v);
}
}
}
void run() {
for(int i = 0; i <= n; i++) head[i] = -1; tot = 0;
for(int i = 1; i <= n; i++) cin >> w[i], d[i] = 0;
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
adde(u, v); adde(v, u);
++d[u], ++d[v];
}
int s; cin >> s;
for(int i = 1; i <= n; i++) vis[i] = false, dis[i] = 0;
if(m == n - 1) {
dis[s] = w[s];
dfs(s);
cout << *max_element(dis + 1, dis + n + 1) << '\n';
return;
}
queue <int> q;
for(int i = 1; i <= n; i++) if(d[i] == 1) q.push(i);
while(!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 1;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(vis[v]) continue;
nxt[u] = v;
if(--d[v] == 1) {
q.push(v);
}
}
}
ll ans = 0;
while(vis[s]) {
ans += w[s]; w[s] = 0;
s = nxt[s];
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
ans += w[i]; w[i] = 0;
}
}
for(int i = 0; i <= n; i++) vis[i] = 0;
dfs(s);
ans += *max_element(dis + 1, dis + n + 1);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n >> m) run();
return 0;
}