这套题不难，但是场上数据水，导致有很多叉点
A.
因为是让求删掉一个后字典序最小，那么当a[i]>a[i+1]的时候，删掉a[i]一定最优！这个题有个叉点，当扫完一遍如果没有满足条件的，就删去最后一个字符。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <stack> using namespace std;
const double eps = 1e-;
const int MOD=1e9+;
typedef long long LL;
typedef unsigned long long ull;
const int INF=;
const LL inf = 1e18;
LL gcd(LL a,LL b){
if(!b)return a;
return gcd(b,a%b);
}
LL lcm(LL a,LL b){
return a/gcd(a,b)*b;
}
const int maxn=2e5+;
char s[maxn];
int n;
int main(){
scanf("%d",&n);
scanf("%s",s);
int pos=-;
for(int i=;i<n-;i++){
if(s[i+]<s[i]){
pos=i;
break;
}
}
if(pos==-)
pos=n-;
for(int i=;i<n;i++)
if(i!=pos)
printf("%c",s[i]);
return ;
}
B.
当n是偶数的时候一定是每次都减2，也就是n/2.当n奇数的时候，就暴力减质数一直减到是偶数或者为0.注意要特判当前n是不是质数。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <stack> using namespace std;
const double eps = 1e-;
const int MOD=1e9+;
typedef long long LL;
typedef unsigned long long ull;
const int INF=;
const LL inf = 1e18;
LL gcd(LL a,LL b){
if(!b)return a;
return gcd(b,a%b);
}
LL lcm(LL a,LL b){
return a/gcd(a,b)*b;
}
const int maxn=2e5+; int prime[maxn];
int vis[maxn];
int num;
int init(int n){
int m = (int)sqrt(n);
vis[]=; for(int i = ;i<=m;i++){
for(int j =i*i; j<=n;j+=i){
vis[j]=;
}
}
for(int i=;i<=n;i++){
if(!vis[i]){
num++;
prime[num] = i;
}
}
return num;
}
bool judge(LL x){
int m =(int)sqrt(x);
for(int i=;i<=m+;i++){
if(x%i==)
return false;
}
return true;
}
LL n;
int
main(){
cin>>n;
LL ans=;
init(2e5);
if(n%==){
cout<<n/<<endl;
return ;
}
bool ok=;
while(n%){
if(judge(n)){
ans+=;
ok=;
break;
} int flag=;
for(int i=;i<=num&&prime[i]<=n;i++){
if(n%prime[i]==){
// printf("!!%d\n",prime[i]);
flag=prime[i];
break;
}
}
//printf("%d\n",flag);
if(!flag)flag=n;
n-=flag;
ans++;
}
if(ok)
ans+=n/;
cout<<ans<<endl;
return ;
}
C.
这个题就是解一个一元二次方程，应该也可以三分来做。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <stack> using namespace std;
const double eps = 1e-;
const int MOD=1e9+;
typedef long long LL;
typedef unsigned long long ull;
const int INF=;
const LL inf = 1e18;
LL gcd(LL a,LL b){
if(!b)return a;
return gcd(b,a%b);
}
LL lcm(LL a,LL b){
return a/gcd(a,b)*b;
}
int main(){
int T;
scanf("%d",&T); int d;
for(int kas=;kas<=T;kas++){
scanf("%d",&d);
double del = d*d - *d;
if(del<){
printf("N\n");
}else if(del == ){
double ans=(double)d/; printf("Y %.9f %.9f\n",ans,(double)(d-ans));
}else{
double ans1 = (double)(d+sqrt(del))/;
if(ans1<=d){
printf("Y %.9f %.9f\n",ans1,(double)(d-ans1));
}else{
double ans1 = (double)(d-sqrt(del))/;
if(ans1<){
printf("N\n");
}else
printf("Y %.9f %.9f\n",ans1,(double)(d-ans1));
}
}
}
return ;
}
D.
最短路+贪心；我们先跑出最短路树来，如果k大于等于最短路树的边数，则树上的边全留下。否则的话就要删树上的边，删哪些呢？从最远（d[u]最大）的边开始删一定是最优的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <stack> using namespace std;
const double eps = 1e-;
const int MOD=1e9+;
typedef long long LL;
typedef unsigned long long ull;
const int INF=;
const LL inf = 1e18;
LL gcd(LL a,LL b){
if(!b)return a;
return gcd(b,a%b);
}
LL lcm(LL a,LL b){
return a/gcd(a,b)*b;
}
const int maxn=3e5+;
int head[maxn],to[*maxn],Next[*maxn],w[*maxn],id[*maxn];
struct Edge{
int from,to,w,id;
};
vector<Edge>edges;
int sz,n,m,k;
void init(){
sz=;
memset(head,-,sizeof(head));
}
void add_edge(int a,int b,int c,int d){
++sz;
to[sz]=b;
w[sz]=c;
id[sz]=d;
Next[sz]=head[a];
head[a]=sz;
}
struct HeapNode{
int u;
LL d;
int from;
bool operator <(const HeapNode& rhs)const{
return d>rhs.d;
}
};
int done[maxn],p[maxn];
LL d[maxn]; Edge edge[maxn]; priority_queue<HeapNode>q;
void dij(){
q.push((HeapNode){,,-});
for(int i=;i<=n;i++)
d[i]=inf;
while(!q.empty()){
HeapNode x= q.top();q.pop();
if(done[x.u])
continue;
done[x.u]=;
d[x.u] = x.d;
p[x.u] = x.from;
//printf("%d\n",x.from);
for(int i=head[x.u];i!=-;i=Next[i]){
int v = to[i];
if(d[v]>d[x.u]+w[i]){
q.push((HeapNode){v,d[x.u]+w[i],id[i]});
}
}
}
} struct Node{
int u;
LL d;
int from;
bool operator <(const Node &rhs)const{
return d<rhs.d;
}
};
int vis[maxn]; priority_queue<Node>Q; int main(){
scanf("%d%d%d",&n,&m,&k); init();
for(int i=;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c,i);
add_edge(b,a,c,i);
edge[i]=(Edge){a,b,c,i};
}
dij();
for(int i=;i<=n;i++){
//printf("@%d\n",p[i]);
if(p[i]!=-&& !vis[p[i]]){
edges.push_back(edge[p[i]]);
vis[p[i]]=;
Q.push((Node){i,d[i],p[i]});
// printf("!!!%d %d %d %d\n",edge[p[i]].from,edge[p[i]].to,edge[p[i]].w,p[i]);
}
}
if(edges.size()<=k){
printf("%d\n",edges.size());
for(int i=;i<edges.size();i++){
printf("%d ",edges[i].id);
}
}else{
int num = edges.size();
while(num>k&&!Q.empty()){
Q.pop();
num--;
}
printf("%d\n",k);
while(!Q.empty()){
printf("%d ",Q.top().from);
Q.pop();
}
}
return ;
}
E.
树状数组或者线段树维护一下。因为每个点的值只可能是来自于它的祖先结点，所以跑dfs的时候，进入这个点的时候更新树状数组，退栈的时候还原树状数组
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector> using namespace std;
const int maxn=3e5+;
typedef long long LL;
int head[maxn],to[*maxn],Next[*maxn];
int n,sz,m;
void add_edge(int a,int b){
sz++;
to[sz]=b;Next[sz]=head[a];head[a]=sz;
}
int lowbit(int x){
return x&(-x);
}
LL sumv[maxn];
void update(int x,int v){
while(x<=n){
sumv[x]+=v;
x+=lowbit(x);
}
}
LL query(int x){
LL res=;
while(x){
res+=sumv[x];
x-=lowbit(x);
}
return res;
}
struct Node{
int d,x;
};
vector<Node>V[maxn];
int fa[maxn],dep[maxn];
LL ans[maxn]; void dfs(int u,int Fa,int depth){
fa[u]=Fa;
dep[u]=depth;
for(int i=;i<V[u].size();i++){
Node N = V[u][i];
update(min(N.d+depth,n),N.x);
}
ans[u] = query(n)-query(depth-);
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(v==Fa)continue;
dfs(v,u,depth+);
}
for(int i=;i<V[u].size();i++){
Node N = V[u][i];
update(min(N.d+depth,n),-N.x);
}
} int main(){
scanf("%d",&n);
memset(head,-,sizeof(head));
for(int i=;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
add_edge(a,b);
add_edge(b,a);
}
scanf("%d",&m);
for(int i=;i<=m;i++){
int v,d,x;
scanf("%d%d%d",&v,&d,&x);
V[v].push_back((Node){d,x});
}
dfs(,-,);
for(int i=;i<=n;i++){
printf("%I64d ",ans[i]);
}
return ;
}
F.
贪心+分类讨论。
每一页多的为Max，少的为Min。那么一定是用少的将多的分隔开。所以如果大小关系不同则不会产生影响。否则的话，这一页我们要它最左边多出来的那块尽量长。lef=k-lastR;那么Max=Max-lef,Min=Min-1;然后我们分类讨论：
1.ceil(Max/k)-1>Min 则return false;
2.ceil(Max/k)<=Min
则说明右边不会剩下。则lastR=0。
3.ceil(Max/k)==Min-1的话，恰好被分割开，右边会有剩余，但是剩余的长度<=k，属于合法。
lastR= Max%k ==0?k:Max%k
这个也有叉点，要主要Min==Max的情况
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib> using namespace std;
const int maxn = 3e5 + ;
int n, k;
int x[maxn][];//0 x,1 y
int state,laststate,lastR;
int main(){
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++){
scanf("%d", &x[i][]);
}
for(int i = ; i <= n; i++){
scanf("%d", &x[i][]);
}
bool flag = ;
for(int i = ; i <= n; i++){ //x >= y state = 1;else state = 0;
int Min = min(x[i][], x[i][]);
int Max = max(x[i][], x[i][]);
// printf("%d %d\n",Min,Max);
if(x[i][] > x[i][])
state = ;
else if(x[i][] < x[i][])
state = ;
else state = -;
if(state == laststate||laststate == -||state == -){
int lef = k - lastR;
Max = Max - lef;
Min = Min - ;
}
//printf("%d %d\n",(int)ceil((double)Max/k),Min); if((int)ceil((double)Max/k)- > Min){
flag = ;
break;
}else if((int)ceil((double)Max/k) <= Min){
lastR = ;
}else{
lastR = Max%k == ?k:Max%k;
}
laststate = state;
}
if(!flag){
printf("NO\n");
}else{
printf("YES\n");
}
return ;
}
G.
好像是打反转标记的线段树，留坑