留念
C – 志愿者
排序。。按照题目规则说的排就可以。wa了两发我太菜了qwq
#include
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c b.t * b.k) return 1;
else if(t * k < b.t * b.k) return 0;
if(t > b.t) return 1;
else if(t < b.t) return 0;
return id < b.id;
}
}a[MAXN];
int main() {
int N = read();
for(int i = 1; i
D – 终端
模拟一下就行了吧。。
#include
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c mp;
string opt;
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
int N = read();
for(int i = 1; i > opt;
if(opt == "touch") {
string fn;
cin >> fn;
if(mp.find(fn) != mp.end()) continue;
mp[fn] = i;
} else if(opt == "rm") {
string fn;
cin >> fn;
if(mp.find(fn) == mp.end()) continue;
mp.erase(fn);
} else if(opt == "ls") {
vector> tmp;
for(auto &x: mp) {
tmp.push_back(make_pair(x.second, x.first));
}
sort(tmp.begin(), tmp.end());
for(auto x: tmp)
cout << x.second << '\n';
} else if(opt == "rename") {
string s1, s2;
cin >> s1 >> s2;
if(mp.find(s1) == mp.end()) continue;
int tmp = mp[s1];
mp.erase(s1);
mp[s2] = tmp;
}
}
return 0;
}
E – 运气
显然每个位置只能是1-6,因此所有状态数是(6^{10})不会很大,dfs一下
#include
using namespace std;
const int MAXN = 1e6 + 10;
const int mod = 1e9 + 7;
#define LL long long
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c
F – 游戏
首先题目有个bug,没有描述序列中有相同数的情况
那就假设所有数都不相同
可以分两种情况考虑,(c1 < c2)和(c1 > c2),相等的话直接输出((N – 1) * c1)就行。
这两种是类似的,这里只说第一种。
显然,数组中的每一对数都有两种情况:1.异或之后二进制位仅有1位为1,2.有多位唯一。
接下来我是转化成了图论问题去考虑,不然感觉有点复杂。
我们把所有异或之后二进制位仅有1个1的点之间连边。
考虑得到的这张图的性质:
对于任意一个联通块,我们一定能通过使用c1代价来每次消掉一个元素,并能保证最后只剩下一个元素。
emmm,,至于为什么,,可以从联通块中抽出一个树来,显然每次从叶子节点删,一定满足条件。
这样的话,只需要dfs出所有联通块,并求出其大小就好。
然后加加减减把答案算出来,具体看代码
复杂度(O(n^2))(实际上还可以优化为(O(nlogn)),这里不再赘述)
#include
using namespace std;
const int MAXN = 1e6 + 10;
const int mod = 1e9 + 7;
#define LL long long
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c v[MAXN];
void dfs(int x) {
cnt++;
vis[x] = 1;
for(auto &to: v[x]) {
if(!vis[to])
dfs(to);
}
}
void dfs2(int i) {
cnt++;
vis[i] = 1;
for(int j = 1; j
G – 森林
(好久没打比赛,开场还以为是个LCT,后来又想操作子树的好像是ETT,不过还好及时终止了自己的危险想法)
感觉这题思维上比上一题简单不少,
对于第一个删边比较难操作
可以倒序考虑转化成加边。
然后并查集维护连通性就ok了
具体看代码
#include
using namespace std;
const int MAXN = 1e6 + 10;
const int mod = 1e9 + 7;
#define LL long long
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c ans;
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
N = read(); M = read();
for(int i = 1; i = 1; i--) {
if(op[i].opt == 1) {
int id = op[i].a;
unionn(E[id].u, E[id].v);
} else if(op[i].opt == 2) {
int id = op[i].a, pre = val[id];
int fx = find(id);
sum[fx] -= pre;
sum[fx] += op[i].b;
val[id] = op[i].b;
} else {
ans.push_back(query(op[i].a));
}
}
reverse(ans.begin(), ans.end());
for(auto &x: ans) cout << x << '\n';
return 0;
}
/*
*/
Original: https://www.cnblogs.com/zwfymqz/p/14165004.html
Author: 自为风月马前卒
Title: 第三届“传智杯”全国大学生IT技能大赛(初赛A组)题解
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/541746/
转载文章受原作者版权保护。转载请注明原作者出处!