第一次打CF，听大佬说是这场是教育场，看时间比较合适就打了。
Educational Codeforces Round 54 [Rated for Div. 2]
A. Minimizing the String
1s, 256M
题意：给一个字符串，删一个字母，使得字典序最小
思路：找第一个前一个比后一个字母字典序大的位置记录下来，删掉就行。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
string s;
int n;
int main() {
cin >> n;
cin >> s;
int mark = n-1;
for(int i = 0; i < n-1; ++i) {
if(s[i] > s[i+1]) {
mark = i;
break;
}
}
for(int i = 0; i < n; ++i) {
if(i == mark) continue;
printf("%c", s[i]);
}
printf("\n");
return 0;
}
B. Divisor Subtraction
2s, 256M
题意：给出一个数字，进行下面三步操作：
1.若n == 0 结束运算
2.找n的最小质因子d
3.n-d并回到step1
输出进行了多少次运算。
思路：很明显，如果这个数本来就是质数，那么只需要1步：减去它自身。但是如果是非质数，如果直接模拟，到找到它变成质数再一步变0也肯定会T。观察几个数字我们发现，如果这个数是偶数，那它的最小质因子必然是2，而它-2之后还是偶数，那么操作步数必然是n/2；而如果是奇数，找第一个质因子（必然也是奇数），相减变成偶数，然后又回到循环-2的情况。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
bool isprimer(ll n) {
ll a = sqrt(n) + 1;
for(ll i = 2; i < a; ++i)
if(n % i == 0)
return false;
return true;
}
int main() {
ll n;
scanf("%lld", &n);
ll cnt;
if(!(n & 1)) {
cnt = n / 2;
}
else {
if(isprimer(n)) {
cnt = 1;
}
else {
for(ll i = 3; i < n; i +=2) {
if(n % i == 0) {
if(isprimer(i)) {
n -= i;
break;
}
}
}
cnt = n / 2 + 1;
}
}
printf("%lld", cnt);
return 0;
}
C. Meme Problem
1s, 256M
题意：给出一个非负整数，问是否存在两个非负实数
，
使得
且
input
7
69
0
1
4
5
999
1000
output
Y 67.985071301 1.014928699
Y 0.000000000 0.000000000
N
Y 2.000000000 2.000000000
Y 3.618033989 1.381966011
Y 997.998996990 1.001003010
Y 998.998997995 1.001002005
思路：刚刚看到题的时候看到 和
也是往数学上想了一点点，但是发现这个如果是Y的a和b必然是一个1～2的数字和d-2～d-1的数字，故二分WA到怀疑人生……
赛后：
可能是我数学太差了8，这个题应该利用初中数学的韦达定理构造一元二次方程orz……
因为我们知道
在一元二次方程中
有韦达定理：
我们令 即令
即
构造一元二次方程，，令
，
因为即
即
故可构造出仅有系数的一元二次方程
如果则无解；
若那么就可以直接求解：
，
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
#define eps 1e-9
int main() {
int T, d;
scanf("%d", &T);
while(T--) {
scanf("%d", &d);
double dd = (double)d;
double delta = dd * dd - 4 * dd;
if(delta < 0) {
printf("N\n");
}
else {
printf("Y %.9f %.9f\n", (dd + sqrt(delta))/2.0, (dd - sqrt(delta))/2.0);
}
}
return 0;
}
D. Edge Deletion
2.5s, 256M
题意：给出一个个点、
条边的无向图（无自环、无重边），
到
点的最短路是
，现在删掉一些边，若
到
的最短路依旧是
，那么称
是好点。现在需要你删去一些边，至多剩下
条边，使得好点的数量尽量的多。
(,
,
,
)
第一行输出需要保留的边的条数，第二行输出保留的边的序号（按照输入顺序标号为
～
）
思路：可以证明按优先队列跑出来的dij树是可行的，因为每次对于已经选中的点，走的路径都是最短，所以对于一个点，最短路虽然有很多，但选中的那条一定是从开始就一直最短的。直接跑出来dij树，尽量删叶子结点，也就是从后往前删边（dij树从后往前删边就是从长往短删），其实这里不用倒着删，直接取dij跑出来的前条边即可。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 3e5 + 5;
int n, m, k;
struct edge { int to, cost; };
map<P, int> mp;
vector<edge> G[maxn];
vector<int> vec, anslist;
bool vis[maxn], vis1[maxn];
ll d[maxn];
int pre[maxn];
void dij() {
priority_queue<P, vector<P>, greater<P> > que;
int v, l;
for(int i = 1; i <= n; ++i)
d[i] = INF;
d[1] = 0;
que.push(P(0, 1));
while(!que.empty()) {
P now = que.top();
que.pop();
v = now.second;
vec.push_back(v);
if(d[v] < now.first)
continue;
l = (int)G[v].size();
for(int i = 0; i < l; ++i) {
edge e = G[v][i];
if(d[e.to] > d[v] + e.cost) {
pre[e.to] = v;
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}
vector<int> findway(int v) {
vector<int> way;
int pr = pre[v];
way.push_back(v);
while(pr != 1) {
way.push_back(pr);
pr = pre[pr];
if(vis1[pr])
break;
vis1[pr] = true;
}
way.push_back(pr);
reverse(way.begin(), way.end());
return way;
}
void solve() {
int l_ = vec.size();
int v, l, st, ed, id;
for(int i = 1; i < l_; ++i) {
v = vec[i];
vector<int> way = findway(v);
l = way.size();
for(int j = 0; j < l - 1; ++j) {
st = way[j], ed = way[j+1];
id = mp[P(st, ed)];
if(!vis[id]) {
vis[id] = true;
anslist.push_back(id);
}
}
if(anslist.size() >= k)
return;
}
return;
}
int main() {
int fr, to, cost;
scanf("%d%d%d", &n, &m, &k);
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", &fr, &to, &cost);
mp[P(fr, to)] = i + 1;
mp[P(to, fr)] = i + 1;
G[fr].push_back((edge){to, cost});
G[to].push_back((edge){fr, cost});
}
dij();
if(k > n-1)
k = n-1;
solve();
printf("%d\n", k);
for(int i = 0; i < k; ++i) {
if(i != 0) printf(" ");
printf("%d", anslist[i]);
}
return 0;
}
我丑陋的代码跑了1060ms……
附：队友跑了467ms的代码
E. Vasya and a Tree
2s, 256M
题意：给你一棵以1为根的有n个点的树，每个点的权值最初为0。有m个操作，每次操作有三个变量，操作为在v的距离
的子树内所有节点权值
，最终统计树上每个点的权值。
思路：先从根1开始，跑一次dfs把树存下来，然后每次操作都跑dfs，路径超过d就返回 -> TLE on test 7
*TLE代码（好像是线段树/树状数组…待补）
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
struct node {
int u, v;
}p[maxn];
vector<int> g[maxn], G[maxn];
ll cost[maxn];
int n, m;
bool vis1[maxn], vis[maxn];
void dfs(int v, int d, int x) {
cost[v] += x;
if(d == 0) return;
for(int i = 0; i < (int)G[v].size(); ++i) {
int u = G[v][i];
if(!vis[u]) {
vis[u] = true;
dfs(u, d-1, x);
vis[u] = false;
}
}
return;
}
void CreateTree(int u) {
for(int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if(!vis1[v]) {
vis1[v] = true;
G[u].push_back(v);
CreateTree(v);
}
}
return ;
}
int main() {
int v, d, x;
scanf("%d", &n);
for(int i = 0; i < n-1; ++i) {
scanf("%d%d", &p[i].u, &p[i].v);
g[p[i].u].push_back(p[i].v);
g[p[i].v].push_back(p[i].u);
}
vis1[1] = true;
CreateTree(1);
scanf("%d", &m);
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", &v, &d, &x);
vis[v] = true;
dfs(v, d, x);
vis[v] = false;
}
for(int i = 1; i <= n; ++i) {
if(i != 1) printf(" ");
printf("%lld", cost[i]);
}
return 0;
}
F. Summer Practice Report
2s, 256M
G. Array Game
6s, 512M
