1 second
256 megabytes
Description:
You are given a string ss consisting of nn 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 s=s1s2…sns=s1s2…sn is lexicographically smaller than string t=t1t2…tmt=t1t2…tm if n<mn<m and s1=t1,s2=t2,…,sn=tns1=t1,s2=t2,…,sn=tn or there exists a number pp such that p≤min(n,m)p≤min(n,m) and s1=t1,s2=t2,…,sp−1=tp−1s1=t1,s2=t2,…,sp−1=tp−1 and sp<tpsp<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 nn (2≤n≤2⋅1052≤n≤2⋅105 ) — the length of ss .
The second line of the input contains exactly nn lowercase Latin letters — the string ss .
Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string ss .
In the first example you can remove any character of ss to obtain the string "aa".
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+;
char s[N];
int n; int main(){
scanf("%d",&n);getchar();
for(int i=;i<=n;i++) scanf("%c",&s[i]);
int i,pos=n;
for(i=;i<n;i++){
int j=i+;
if(s[j]<s[i]){
pos=i;
break ;
}
}
for(int i=;i<=n;i++){
if(i==pos) continue ;
printf("%c",s[i]);
}
return ;
}
2 seconds
256 megabytes
Description:
You are given an integer number nn. The following algorithm is applied to it:
- if n=0, then end algorithm;
- find the smallest prime divisor d of n;
- subtract d from n and go to step 1.
Determine the number of subtrations the algorithm will make.
The only line contains a single integer nn (2≤n≤10102≤n≤1010).
Print a single integer — the number of subtractions the algorithm will make.
In the first example 5 is the smallest prime divisor, thus it gets subtracted right away to make a 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 = ;
for(int i=;i<=sqrt(x+0.5)+;i++){
if(x%i==){
flag=;break ;
}
}
return flag;
} int main(){
scanf("%lld",&n);
if(n%==){
printf("%lld",n/);return ;
}
if(prim(n)){
printf("");return ;
}
for(int i=;i<=sqrt(n+0.5)+;i++){
if(n%i== && prim(i)){
printf("%lld",+(n-i)/);
return ;
}
}
return ;
}
1 second
256 megabytes
Try guessing the statement from this picture:
You are given a non-negative integer dd . You have to find two non-negative real numbers aa and bb such that a+b=d and a⋅b=d .
The first line contains tt (1≤t≤1031≤t≤103 ) — the number of test cases.
Each test case contains one integer d (0≤d≤103) .
For each test print one line.
If there is an answer for the i -th test, print "Y", and then the numbers a and b .
If there is no answer for the i -th test, print "N".
Your answer will be considered correct if |(a+b)−a⋅b|≤10−6|(a+b)−a⋅b|≤10−6 and |(a+b)−d|≤10−6|(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-; int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
if(n==){
printf("Y 0.000000000 0.000000000\n");
continue ;
}else if(n== || n== ||n==){
printf("N\n");continue;
}else if(n==){
printf("Y 2.000000000 2.000000000\n");
continue ;
}else{
double l = ,r=,mid,Ans,tmp;
while(l<=r){
mid=(l+r)/;
tmp = n-mid;
if(abs(tmp*mid-tmp-mid)<eps || abs(tmp*mid-n)<eps){
Ans=mid;break;
}
if(tmp*mid-tmp-mid<) l=mid+0.0000000001;
else r=mid-0.0000000001;
}
printf("Y %.9lf %.9lf\n",n-Ans,Ans);
}
} return ;
}
2.5 seconds
256 megabytes
Description:
You are given an undirected connected weighted graph consisting of nn vertices and mm edges. Let's denote the length of the shortest path from vertex 11 to vertex ii as didi .
You have to erase some edges of the graph so that at most kk edges remain. Let's call a vertex ii good if there still exists a path from 11 to ii with length didi 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 nn , mm and kk (2≤n≤3⋅1052≤n≤3⋅105 , 1≤m≤3⋅1051≤m≤3⋅105 , n−1≤mn−1≤m , 0≤k≤m0≤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 mm lines follow, each containing three integers xx , yy , ww (1≤x,y≤n1≤x,y≤n , x≠yx≠y , 1≤w≤1091≤w≤109 ), denoting an edge connecting vertices xx and yy and having weight ww .
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 ee — the number of edges that should remain in the graph (0≤e≤k0≤e≤k ).
In the second line print ee distinct integers from 11 to mm — the indices of edges that should remain in the graph. Edges are numbered in the same order they are given in the input. The number of 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+;
int n,m,k;
int vis[N]={};
LL d[N];
pli pre[N];
vector<pair<int,pii> > vec[N];
vector<int> ans ;
void Dij(int x){
fill(d,d+n+,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]=;
for(int i=;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=;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=,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();
bfs(,k);
printf("%d\n",ans.size());
for(int i=;i<ans.size();i++) printf("%d ",ans[i]);
return ;
}