A. Minimizing the String
You are given a string s consisting of 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 s=s1s2…sn is lexicographically smaller than string t=t1t2…tm if n<m and s1=t1,s2=t2,…,sn=tn or there exists a number p such that p≤min(n,m) and s1=t1,s2=t2,…,sp−1=tp−1 and sp<tp.
For example, "aaa" is smaller than "aaaa", "abb" is smaller than "abc", "pqr" is smaller than "z".
Input
The first line of the input contains one integer n(2≤n≤2e5) — the length of s.
The second line of the input contains exactly n lowercase Latin letters — the string s.
Output
Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string s.
题目大意
给一个字符串，去除一个字母，使得字符串字典序最小
思路
贪心找到第一个s[i]>s[i+1]，去除s[i]即可
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 2e5 + 100;
char str[maxn];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",str);
int vis = n-1;
for(int i=0; i<n-1; i++)
{
if(str[i]>str[i+1])
{
vis = i;
break;
}
}
for(int i=0; i<n; i++)
{
if(vis!=i)
printf("%c",str[i]);
}
return 0;
}
B. Divisor Subtraction
You are given an integer number n. The following algorithm is applied to it:
1.if n=0, then end algorithm;
2.find the smallest prime divisor d of n;
3.subtract d from n and go to step 1;
Determine the number of subtrations the algorithm will make.
Input
The only line contains a single integer n
(2≤n≤1e10).
Output
Print a single integer — the number of subtractions the algorithm will make.
题目大意
给一个n，如果n等于0停止算法并且输出执行减法几次，否则找出最小的质因数d，并且减去d，再次判断是否为0.
题目思路
如果完全按照题目描述写代码肯定超时。
我们分奇偶考虑：
如果n为偶数，最小的质因数一定是2，那么一直减2直到为0，减法次数为n/2。
如果n为奇数，那么找到它最小的质因数只需要O(sqrt)的时间复杂度，并且质因数一定是奇数，然后执行n为偶数。
总时间复杂度为O(n)。n<1e10
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
ll solve(ll n)
{
ll ans = 0;
while(n)
{
if(n%2==0)
{
ans+=(n/2);
break;
}
ll Max_n = sqrt(n+1);
ll cnt = 0;
for(ll i=3; i<=Max_n ; i+=2)
{
if(n%i==0)
{
cnt = n/i;
ans ++;
n = n - i;
break;
}
}
if(cnt==0)
{
ans++;
break;
}
}
return ans;
}
int main()
{
ll n;
scanf("%I64d",&n);
printf("%I64d\n",solve(n));
return 0;
}
C. Meme Problem
Try guessing the statement from this picture:
You are given a non-negative integer d. You have to find two non-negative real numbers a and b such that a+b=d and a⋅b=d.
Input
The first line contains t(1≤t≤1e3) — the number of test cases.
Each test case contains one integer d(0≤d≤1e3).
Output
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|≤1e−6 and |(a+b)−d|≤1e−6.
题目大意
给定一个d，求满足a+b=d且a*b=d a,b的值
题目思路
求解方程的到 (a-0.5d)^2 = 0.25d^2-d
如果右边小于0则无解，否则解出a再求b
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
double d,a,b;
scanf("%lf",&d);
double c = 0.25*d*d-d;
if(c<0)
puts("N");
else
{
c = sqrt(c);
a = c + 0.5*d;
b = d - a;
printf("Y %.9f %.9f\n",a,b);
}
}
return 0;
}
D. Edge Deletion
You are given an undirected connected weighted graph consisting of nn vertices and m edges. Let's denote the length of the shortest path from vertex 1 to vertex i 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 1 to i with length di after erasing the edges.
Your goal is to erase the edges in such a way that the number of good vertices is maximized.
Input
The first line contains three integers nn, mm and kk (2≤n≤3⋅e5,1≤m≤3e5,n−1≤m,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 mm lines follow, each containing three integers x, y, w (1≤x,y≤n, x≠y, 1≤w≤1e9), denoting an edge connecting vertices x and y 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).
Output
In the first line print ee — the number of edges that should remain in the graph (0≤e≤k).
In the second line print ee distinct integers from 1 to m — 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.
题目大意
给一张n个点，m条边的无向带权图。保留k条边后最多能有几个点和1的最短路不会变。求出几个点，并且求出保留哪几条变。
思路
在求出最短路的过程中记录哪些边是在最短路上的即可。时间复杂度O(n*log(n)) n<=3e5
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = 3e5 + 100 ;
struct Edge {
int to, next, id;
ll w;
} edge[maxn*2];
int first[maxn],sign;
void init() {
memset(first, -1, sizeof(first));
sign = 0;
}
void add_edge(int id,int u, int v, ll w) {
edge[sign].id = id;
edge[sign].to = v;
edge[sign].w = w;
edge[sign].next = first[u];
first[u] = sign++;
}
struct point
{
int x,id;
ll w;
point(){}
point(int xx,int iid,ll ww){x=xx,id=iid,w=ww;}
friend bool operator<(point a,point b)
{
return a.w>b.w;
}
}now;
priority_queue<point>q;
vector<int>answer;
int MinLen[maxn],vis[maxn];
void dij(int n,int m)
{
for(int i=1;i<=n;i++)MinLen[i]=-1;
memset(vis,0,sizeof(vis));
q.push(point(1,0,0));
while(!q.empty())
{
now = q.top();
q.pop();
if(vis[now.x])continue;
MinLen[now.x]=now.w;
vis[now.x]=1;
answer.push_back(now.id);
for(int i=first[now.x];~i;i=edge[i].next)
{
q.push(point(edge[i].to,edge[i].id,edge[i].w+now.w));
}
}
int ans = answer.size()-1;
ans = min(ans,m);
printf("%d\n",ans);
if(ans)
printf("%d",answer[1]);
for(int i=2;i<=ans;i++)
{
printf(" %d",answer[i]);
}
}
int main()
{
init();
int n,m,k,x,y;
ll w;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d%d%I64d",&x,&y,&w);
add_edge(i,x,y,w);
add_edge(i,y,x,w);
}
dij(n,k);
return 0;
}
E. Vasya and a Tree
Vasya has a tree consisting of n vertices with root in vertex 1. At first all vertices has 0 written on it.
Let d(i,j)d(i,j) be the distance between vertices i and j, i.e. number of edges in the shortest path from i to j. Also, let's denote k-subtree of vertex x — set of vertices y such that next two conditions are met:
x is the ancestor of y (each vertex is the ancestor of itself);
d(x,y)≤k.
Vasya needs you to process mm queries. The i-th query is a triple vivi, didi and xi. For each query Vasya adds value xixi to each vertex from di-subtree of vi.
Report to Vasya all values, written on vertices of the tree after processing all queries.
Input
The first line contains single integer nn (1≤n≤3e5) — number of vertices in the tree.
Each of next n−1n−1 lines contains two integers x and y (1≤x,y≤n) — edge between vertices x and y. It is guarantied that given graph is a tree.
Next line contains single integer mm (1≤m≤3e5) — number of queries.
Each of next mm lines contains three integers vi, di, xi (1≤vi≤n,0≤di≤1e9,1≤xi≤1e9) — description of the i-th query.
Output
Print nn integers. The i-th integers is the value, written in the i-th vertex after processing all queries.
题目大意
给一颗以1号节点为根，有n个节点的树。节点的初始值都为1，m次操作
,每次操作三个整数v,d,x，每次将以v为祖先，距离小于d的所有儿子节点都加上一个x。求所有操作结束后每个节点的值。
思路
这题需要一些技巧，我们可以在遍历树的时候记录深度多少的节点得到的权值为多少，回溯的时候再消去这个影响。
比如：
1->2->3->4->5->6->7
假设我们进行操作v=2，d=2，x=1
在遍历到2的时候，我们对数组d[]的2到4都加上1，在回溯回2的时候再减去，就可以消除影响了.
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 100;
int n,vis[maxn];
///记录答案
ll answer[maxn];
///存边
vector<int>E[maxn];
///记录更新
struct part
{
int d;
ll x;
part(){}
part(int dd,ll xx){d=dd,x=xx;}
}now;
vector<part>q[maxn];
///线段树部分
struct node
{
int l,r;
ll sum,lazy;
} T[maxn*4];
ll ans=0;
void build(int v,int l,int r)
{
T[v].l=l,T[v].r=r,T[v].lazy = 0;
if(l==r)return ;
int mid = (l+r)>>1;
build(v<<1,l,mid);
build(v<<1|1,mid+1,r);
}
void add(int v,int l,int r,ll value)
{
if(T[v].l==l&&T[v].r==r)
{
T[v].sum+=value*(r-l+1);
T[v].lazy+=value;
return ;
}
int mid=(T[v].l+T[v].r)>>1;
if(T[v].lazy)
{
T[v<<1].sum += T[v].lazy * (T[v<<1].r - T[v<<1].l + 1);
T[v<<1|1].sum += T[v].lazy * (T[v<<1|1].r - T[v<<1|1].l + 1);
T[v<<1].lazy += T[v].lazy;
T[v<<1|1].lazy += T[v].lazy;
T[v].lazy=0;
}
if(r<=mid)
add(v<<1,l,r,value);
else
{
if(l>mid)
add(v<<1|1,l,r,value);
else
add(v<<1,l,mid,value),add(v<<1|1,mid+1,r,value);
}
T[v].sum = T[v<<1].sum+T[v<<1|1].sum;
}
void query(int v,int l,int r)
{
if(T[v].l==l&&T[v].r==r)
{
ans += T[v].sum;
return ;
}
int mid=(T[v].l+T[v].r)>>1;
if(T[v].lazy)
{
T[v<<1].sum += T[v].lazy * (T[v<<1].r - T[v<<1].l + 1);
T[v<<1|1].sum += T[v].lazy * (T[v<<1|1].r - T[v<<1|1].l + 1);
T[v<<1].lazy += T[v].lazy;
T[v<<1|1].lazy += T[v].lazy;
T[v].lazy=0;
}
if(r<=mid)
{
query(v<<1,l,r);
}
else
{
if(l>mid)
{
query(v<<1|1,l,r);
}
else
{
query(v<<1,l,mid);
query(v<<1|1,mid+1,r);
}
}
T[v].sum = T[v<<1].sum+T[v<<1|1].sum;
}
void dfs(int now,int deep)
{
for(int i=0;i<q[now].size();i++)
add(1,deep,min(deep+q[now][i].d,300000),q[now][i].x);
ans = 0;
query(1,deep,deep);
answer[now]=ans;
for(int i=0;i<E[now].size();i++)
{
if(vis[E[now][i]])continue;
vis[E[now][i]] = 1;
dfs(E[now][i],deep+1);
}
for(int i=0;i<q[now].size();i++)
add(1,deep,min(deep+q[now][i].d,300000),-q[now][i].x);
}
int main()
{
int m;
scanf("%d",&n);
build(1,1,300000);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
E[x].push_back(y),E[y].push_back(x);
}
scanf("%d",&m);
while(m--)
{
int v,d;
ll x;
scanf("%d%d%I64d",&v,&d,&x);
q[v].push_back(part(d,x));
}
vis[1]=1;
dfs(1,1);
printf("%I64d",answer[1]);
for(int i=2;i<=n;i++)
{
printf(" %I64d",answer[i]);
}
return 0;
}