Educational Codeforces Round 54 (Rated for Div. 2) ABCD
Description:
You are given a string n lowercase Latin letters.
You have to remove at most one (i.e. zero or one) character of this string in such a way that the string you obtain will be lexicographically smallest among all strings that can be obtained using this operation.
String sp<tp .
For example, "aaa" is smaller than "aaaa", "abb" is smaller than "abc", "pqr" is smaller than "z".
The first line of the input contains one integer s .
The second line of the input contains exactly s .
Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string s .
In the first example you can remove any character of
In the second example "abca" < "abcd" < "abcda" < "abda" < "acda" < "bcda".
题意：
在序列中至多删去一个数，使得操作后得序列最小（与执行相同操作的其它序列相比）
题解：
通过模拟一下这个过程可以发现我们要找 i 这个位置，满足si>si+1&&i<n 或者直接i=n。
代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int N = 2e5+5; char s[N]; int n; int main(){ scanf("%d",&n);getchar(); for(int i=1;i<=n;i++) scanf("%c",&s[i]); int i,pos=n; for(i=1;i<n;i++){ int j=i+1; if(s[j]<s[i]){ pos=i; break ; } } for(int i=1;i<=n;i++){ if(i==pos) continue ; printf("%c",s[i]); } return 0; }
Description:
You are given an integer number n. The following algorithm is applied to it:
- if , then end algorithm;
- find the smallest prime divisor n;
- subtract .
Determine the number of subtrations the algorithm will make.
The only line contains a single integer 2≤n≤1010).
Print a single integer — the number of subtractions the algorithm will make.
In the first example 0.
In the second example 2 is the smallest prime divisor at both steps.
题意：
找n最小的质因子d，然后减去d，不断 重复这一过程直到n=0。
题解：
n为偶数很容易。当n为奇数时，质因子必为奇数，减去后也为偶数。所以问题的关键就是当n为奇数的情况。
最后发现只要找到一个最小的d，使得n%d==0就可以了，不管d是否为质数。
我当时没考虑到这一点，所以代码有点丑陋。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; long long n; inline int prim(int x){ int flag = 1; for(int i=2;i<=sqrt(x+0.5)+1;i++){ if(x%i==0){ flag=0;break ; } } return flag; } int main(){ scanf("%lld",&n); if(n%2==0){ printf("%lld",n/2);return 0; } if(prim(n)){ printf("1");return 0; } for(int i=2;i<=sqrt(n+0.5)+1;i++){ if(n%i==0 && prim(i)){ printf("%lld",1+(n-i)/2); return 0; } } return 0; }
Try guessing the statement from this picture:
You are given a non-negative integer a⋅b=d .
The first line contains 1≤t≤103 ) — the number of test cases.
Each test case contains one integer (0≤d≤103) .
For each test print one line.
If there is an answer for the b .
If there is no answer for the
Your answer will be considered correct if |(a+b)−d|≤10−6 .
7 69 0 1 4 5 999 1000
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.00100200
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> using namespace std; int t,n; double eps = 1e-7; int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); if(n==0){ printf("Y 0.000000000 0.000000000 "); continue ; }else if(n==1 || n==2 ||n==3){ printf("N ");continue; }else if(n==4){ printf("Y 2.000000000 2.000000000 "); continue ; }else{ double l = 1,r=2,mid,Ans,tmp; while(l<=r){ mid=(l+r)/2; tmp = n-mid; if(abs(tmp*mid-tmp-mid)<eps || abs(tmp*mid-n)<eps){ Ans=mid;break; } if(tmp*mid-tmp-mid<0) l=mid+0.0000000001; else r=mid-0.0000000001; } printf("Y %.9lf %.9lf ",n-Ans,Ans); } } return 0; }
Description:
You are given an undirected connected weighted graph consisting of di .
You have to erase some edges of the graph so that at most di after erasing the edges.
Your goal is to erase the edges in such a way that the number of good vertices is maximized.
The first line contains three integers 0≤k≤m ) — the number of vertices and edges in the graph, and the maximum number of edges that can be retained in the graph, respectively.
Then w .
The given graph is connected (any vertex can be reached from any other vertex) and simple (there are no self-loops, and for each unordered pair of vertices there exists at most one edge connecting these vertices).
In the first line print 0≤e≤k ).
In the second line print good vertices should be as large as possible.
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #include <vector> #define INF 1e18 using namespace std; typedef long long LL; typedef pair<LL,int> pli; typedef pair<int,int> pii; const int N = 3e5+5; int n,m,k; int vis[N]={0}; LL d[N]; pli pre[N]; vector<pair<int,pii> > vec[N]; vector<int> ans ; void Dij(int x){ fill(d,d+n+2,INF);d[x]=0ll; priority_queue<pli,vector<pli>,greater<pli> > q; q.push(make_pair(d[x],x)); while(!q.empty()){ pli now = q.top();q.pop(); int u = now.second; if(vis[u]) continue ; vis[u]=1; for(int i=0;i<vec[u].size();i++){ int v = vec[u][i].second.first; if(d[v]>d[u]+vec[u][i].second.second &&!vis[v]){ d[v]=d[u]+vec[u][i].second.second; pre[v]=make_pair(u,vec[u][i].first); q.push(make_pair(d[v],v)); } } } } queue <int> que ; void bfs(int x,int K){ que.push(x); while(!que.empty() && K){ int u = que.front();que.pop(); for(int i=0;i<vec[u].size();i++){ int v = vec[u][i].second.first ; if(d[v]==d[u]+vec[u][i].second.second){ que.push(v); ans.push_back(vec[u][i].first); K--; } if(!K) break ; } } } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1,u,v,c;i<=m;i++){ scanf("%d%d%d",&u,&v,&c); vec[u].push_back(make_pair(i,make_pair(v,c))); vec[v].push_back(make_pair(i,make_pair(u,c))); } Dij(1); bfs(1,k); printf("%d ",ans.size()); for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); return 0; }