哎。。本来想写完之后在写博客的，但感觉剩下两道比较难啊，估计要等好久才能写出来了。。
A-Card Stacking
题目链接：https://ac.nowcoder.com/acm/contest/993/A
题目大意：n头牛坐在一圈，按顺序发牌。1,2,3,4,5.。。问自己最后都获得那些牌，从小到大输出自己活得的牌。
思路：简单deque模拟就好了，最后排一下序。
ACCode：
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
// srand(unsigned)time(NULL));rand();
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
deque<int> deq;
int Ans[MAXN];
int n,k,p;
int main(){
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=k;++i) deq.push_back(i);
int peo=2,tmp=0;
while(deq.size()){
if(peo==1) Ans[++tmp]=deq.front();
deq.pop_front();
for(int i=1;i<=p;++i){
deq.push_back(deq.front());deq.pop_front();
}
peo=peo%n+1;
}sort(Ans+1,Ans+tmp+1);
for(int i=1;i<=tmp;++i) printf("%d\n",Ans[i]);
} B-Bookshelf
题目链接：https://ac.nowcoder.com/acm/contest/993/B
题目大意：一个书架高S，每头牛高Hi，n头牛，问最低多高能够超过书架
思路：文少写的，排一下序加起来就好了
ACCode：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll n,b;
scanf("%lld%lld",&n,&b);
ll a[n+3];
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
sort(a,a+n);
ll sum=0;
int f=0;
for(int i=n-1;i>=0;i--){
sum=sum+a[i] ;
f++;
if(sum>=b){
break;
}
}
printf("%d\n",f);
return 0;
} C-Bookshelf 2
题目链接：https://ac.nowcoder.com/acm/contest/993/C
题目大意：还是上道题的意思，问最低的超过S的高度。
思路：数据太小，直接暴力DFS就好了
ACCode：
int A[25];
int n,H;
int DFS(int Sum,int i){
//cout<<Sum<<" "<<i<<endl;
if(Sum>=H) return Sum-H;
if(i==n+1) return INF32;
return min(DFS(Sum+A[i],i+1),DFS(Sum,i+1));
}
int Solve(){
return DFS(0,1);
}
int main(){
scanf("%d%d",&n,&H);
for(int i=1;i<=n;++i) scanf("%d",&A[i]);
printf("%d\n",Solve());
} D-迷路的牛
题目链接：https://ac.nowcoder.com/acm/contest/993/D
题目大意：中文题，比较容易读懂。
思路：最大的就是找到最大的距离，每次只移动挨着。最小移动1次或2次。注意如果一开始就是挨着的都是0.
ACCode：
int main(){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
int Max=max(abs(a-b),abs(b-c))-1,Min=min(abs(a-b),abs(b-c))-1;
if(Max==0&&Min==0) printf("0\n0\n");
else printf("%d\n%d\n",Min==1?1:2,Max);
} E-对牛排序
题目链接：https://ac.nowcoder.com/acm/contest/993/E
题目大意：中文题
思路：神仙写的，类似于找逆序数。
ACCode：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[110];
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
int ans=arr[1];
int flag=1;
for(int i=2;i<=n;i++)
{
if(ans>arr[i])
{
//cout<<ans<<" "<<arr[i]<<endl;
ans=arr[i];
flag=i;
}
else
ans=arr[i];
}
cout<<flag-1<<endl;
return 0;
} F-Mud Puddles
题目链接：https://ac.nowcoder.com/acm/contest/993/F
题目大意：给出一些点不能通过，牛只能上下左右走。问最少多少步走到终点。
思路：数据范围较小，暴力BFS即可。
ACCode：
const int MAXN=1e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
struct Point{
int i,j,size;
Point(int _i=0,int _j=0,int _size=0){
i=_i;j=_j;size=_size;
}
};
int MP[MAXN][MAXN];
int Vis[MAXN][MAXN];
int Fi[5]={0,0,0,1,-1},Fj[5]={0,1,-1,0,0};
Point End;
int n;
int BFS(Point Str){
clean(Vis,INF32);Vis[Str.i][Str.j]=0;
queue<Point> que;que.push(Str);
while(que.size()){
Point u=que.front();que.pop();
if(u.i==End.i&&u.j==End.j) return u.size;
for(int i=1;i<=4;++i){
Point v=Point(u.i+Fi[i],u.j+Fj[i],u.size+1);
if(MP[v.i][v.j]==0&&Vis[v.i][v.j]==INF32){
que.push(v);Vis[v.i][v.j]=v.size;
}
}
}return -1;
}
int main(){
scanf("%d%d%d",&End.i,&End.j,&n);
End.i+=500;End.j+=500;
for(int i=1;i<=n;++i){
int x,y;scanf("%d%d",&x,&y);
x+=500;y+=500;
MP[x][y]=1;
}printf("%d\n",BFS(Point(500,500,0)));
} H-Charm Bracelet
题目链接：https://ac.nowcoder.com/acm/contest/993/H
题目大意：n个物品，每个物品有权值和重量两个属性，找到约束重量的最大权值组合。
思路：简单背包，文少秒A。
ACCode：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
int wi,di;
};
int main(){
ll n,m;
scanf("%lld%lld",&n,&m);
node a[n+3];
for(int i=0;i<n;i++){
scanf("%d%d",&a[i].wi,&a[i].di);
}
ll b[m+3];
memset(b,0,sizeof(b));
ll mx=0;
for(int i=0;i<n;i++){
for(int j=m;j>=a[i].wi;j--){
b[j]=b[j]<b[j-a[i].wi]+a[i].di?b[j-a[i].wi]+a[i].di:b[j];
mx=mx<b[j]?b[j]:mx ;
}
}
printf("%lld\n",mx);
return 0;
} J-Sightseeing Cows
题目链接：https://ac.nowcoder.com/acm/contest/993/J
题目大意：给出一个有向图，每个节点有一个权值val，每条边有一个长度len。奶牛要逛不少于两个点，并且最后要回到原点。求Ans= 所逛过的节点权值之和 / 经过的边的距离之和 的最大Ans。
思路：最优比率环原题：https://blog.csdn.net/qq_40482358/article/details/96325343
ACCode：
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
#define ll long long
#define Pair pair<double,double>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=5e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
struct Node{
int v,nxt;
double len;
Node(int _v=0,double _len=0,int _nxt=0){
v=_v;len=_len;nxt=_nxt;
}
};
Node Edge[MAXN];
int Head[MAXN],Ecnt;
int Stk[MAXN],tot;
double Val[MAXN],Dis[MAXN];
int Vis[MAXN],Cnt[MAXN];
int n,m;
void Intt(){
clean(Head,-1);Ecnt=0;
}
void AddEdge(int a,int b,double val){
Edge[Ecnt]=Node(b,val,Head[a]);
Head[a]=Ecnt++;
}
int Judge(double mid){
for(int i=1;i<=n;++i){
Dis[i]=0;Vis[i]=1;Cnt[i]=1;
Stk[tot++]=i;
}
while(tot){
int u=Stk[--tot];Vis[u]=0;
for(int i=Head[u];i+1;i=Edge[i].nxt){
int v=Edge[i].v;
double temp=Edge[i].len*mid-Val[v];
if(Dis[v]>Dis[u]+temp){
Dis[v]=Dis[u]+temp;
if(Vis[v]==0){
Vis[v]=1;Cnt[v]++;
Stk[tot++]=v;
if(Cnt[v]>n) return 1;
}
}
}
}return 0;
}
int main(){
Intt();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lf",&Val[i]);
}
for(int i=1;i<=m;++i){
double a,b,c;scanf("%lf%lf%lf",&a,&b,&c);
AddEdge(a,b,c);
}
double l=0.0,r=1000.0,mid;
while(l<r-EPS){
mid=(l+r)/2.0;
if(Judge(mid)) l=mid;
else r=mid;
}printf("%.2f\n",r);
} K-Gourmet Grazers
题目链接：https://ac.nowcoder.com/acm/contest/993/K
题目大意：给出n头牛，每头牛有两个属性：金钱，美味。m个产品，每个产品有两个属性：金钱，美味。只有一个产品的两个属性都大于等于牛的时候，这头牛才会去吃这个产品。问使n头牛都能吃上产品，最少花费多少。如果不能满足，输出-1；
思路：贪心+Splay。原题：https://blog.csdn.net/qq_40482358/article/details/96132929
ACCode：
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
// srand(unsigned)time(NULL));rand();
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
class SplayTree{
struct Node{
ll A,B;
int l,r,f,siz;
Node(ll _A=0,ll _B=0,int _l=0,int _r=0,int _f=0,int _siz=0){
A=_A;B=_B;l=_l;r=_r;f=_f;siz=_siz;
}
friend int operator < (Node a,Node b){
if(a.A==b.A) return a.B<b.B;
return a.A<b.A;
}
};
Node Tree[MAXN];
int Lazy[MAXN];
int Rt,Ecnt;//Rt的父节点是0,第一个节点从1开始。
void PushUp(int x){//次序
Tree[x].siz=Tree[Tree[x].l].siz+Tree[Tree[x].r].siz+1;
}
void PushDown(int x){//反转
if(Lazy[x]){
int temp=Tree[x].l;Tree[x].l=Tree[x].r;Tree[x].r=temp;
Lazy[Tree[x].l]^=1;Lazy[Tree[x].r]^=1;
Lazy[x]=0;
}
}
void Rotate(int x,int oper){
int y=Tree[x].f;
PushDown(y);PushDown(x);
if(oper){
Tree[y].r=Tree[x].l;
if(Tree[x].l!=0) Tree[Tree[x].l].f=y;
Tree[x].l=y;
}
else{
Tree[y].l=Tree[x].r;
if(Tree[x].r!=0) Tree[Tree[x].r].f=y;
Tree[x].r=y;
}Tree[x].f=Tree[y].f;
if(Tree[y].f){
if(y==Tree[Tree[y].f].l) Tree[Tree[y].f].l=x;
else Tree[Tree[y].f].r=x;
}Tree[y].f=x;PushUp(y);
}
void Splay(int x,int f){
PushDown(x);
int y=Tree[x].f,z=0;
while(y!=f){
z=Tree[y].f;
PushDown(z);PushDown(y);PushDown(x);
if(z==f) Rotate(x,x==Tree[y].r);
else{
if((x==Tree[y].l^y==Tree[z].l)==0){
Rotate(y,y==Tree[z].r);Rotate(x,x==Tree[y].r);
}
else{
Rotate(x,x==Tree[y].r);Rotate(x,x==Tree[z].r);
}
}PushUp(x);y=Tree[x].f;
}PushUp(x);
if(f==0) Rt=x;
}
int MinNode(ll Key){
int x=Rt,ans=-1;
PushDown(x);
while(1){
if(Tree[x].A>=Key){//该节点可以取得
ans=x;
if(Tree[x].l) x=Tree[x].l;//向左子节点
else return ans;
}
else{//不可以取得
if(Tree[x].r) x=Tree[x].r;//可以的话直接向右走了
else return ans;//没有符合要求的
}
}
}
int GetPre(){
int x=Rt;
if(Tree[x].l) x=Tree[x].l;
else return x;
while(1){
if(Tree[x].r) x=Tree[x].r;
else return x;
}
}
public:
void Intt(){
clean(Lazy,0);
Rt=0;Ecnt=0;
}
void Insert(ll A,ll B){
Tree[++Ecnt]=Node(A,B,0,0,0,1);
int y=0,x=Rt;
while(x){
y=x;
if(Tree[Ecnt]<Tree[x]) x=Tree[x].l;
else if(Tree[x]<Tree[Ecnt]) x=Tree[x].r;
else return ;
}
if(y==0) Rt=Ecnt;
else if(Tree[Ecnt]<Tree[y]){
Tree[y].l=Ecnt;Tree[Ecnt].f=y;
}
else{
Tree[y].r=Ecnt;Tree[Ecnt].f=y;
}Splay(Ecnt,0);
}
ll DeleteMin(ll Key){//所有的B都符合要求，找到最小的A>=P
int Pos=MinNode(Key);
if(Pos==-1) return -1;
ll Ans=Tree[Pos].A;
Splay(Pos,0);
//cout<<"Pos,Pre:"<<Pos<<" "<<GetPre()<<endl;
Splay(GetPre(),0);//cout<<"Debug:\n";Show(Rt);cout<<"End\n";
if(Pos==GetPre()){
Rt=Tree[Rt].r;Tree[Rt].f=0;
}
else{
Splay(Pos,Rt);
Tree[Rt].r=Tree[Pos].r;Tree[Tree[Rt].r].f=Rt;
}
return Ans;
}
//-------
int GetRt(){
return Rt;
}
void Show(int x){
if(x==0) return ;
PushDown(x);
printf("x:%d xf:%d xl:%d xr:%d (A,B)(%lld,%lld)\n",x,Tree[x].f,Tree[x].l,Tree[x].r,Tree[x].A,Tree[x].B);
Show(Tree[x].l);
// printf("A:%lld B:%lld\n",Tree[x].A,Tree[x].B);
Show(Tree[x].r);
}
};
struct Node{
ll P,G;
Node(ll _P=0,ll _G=0){
P=_P;G=_G;
}
friend int operator < (Node a,Node b){
if(a.G==b.G) return a.P<b.P;
return a.G<b.G;
}
};
SplayTree Spl;
Node Cows[MAXN],Goods[MAXN];
int n,m;
int PosX(ll Key,int l,int r){
while(l<=r){
int mid=(l+r)>>1;
if(Goods[mid].G<Key) l=mid+1;
else r=mid-1;
}return l;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld%lld",&Cows[i].P,&Cows[i].G);
for(int i=1;i<=m;++i) scanf("%lld%lld",&Goods[i].P,&Goods[i].G);
sort(Cows+1,Cows+1+n);sort(Goods+1,Goods+1+m);
ll ans=0;int flag=1,tmp=m;
Spl.Intt();
for(int i=n;i>=1;--i){
int Pos=PosX(Cows[i].G,1,tmp);
//printf("P:%lld G:%lld tmp:%d Pos:%d\n",Cows[i].P,Cows[i].G,tmp,Pos);
for(int j=Pos;j<=tmp;++j) Spl.Insert(Goods[j].P,Goods[j].G);
//cout<<"--"<<endl;Spl.Show(Spl.GetRt());cout<<"--"<<endl;
ll temp=Spl.DeleteMin(Cows[i].P);
if(temp==-1){//找最小的花费
flag=0;break;
}
ans+=temp;tmp=Pos-1;
//cout<<"ans:"<<ans<<endl;
}
if(flag==0) printf("-1\n");
else printf("%lld\n",ans);
}
L-Best Cow Line
题目链接：https://ac.nowcoder.com/acm/contest/993/L
题目大意：n个大写字符进行重新排位。只能从头或者尾取出一个放在新的字符串的尾。找出字典序最小的那个串
思路：碰见取小的，如果一样DFS进去比较，找出第一个小的即可。注意输出80个字符就要换行。。眼瞎看不见WA了无数发
ACCode：
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
// srand(unsigned)time(NULL));rand();
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=5e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false);
char S[MAXN];
int Id[MAXN];
int n;
int DFS(int top,int bot){
if(S[top]==S[bot]){
if(top==bot) return 1;
else if(top==bot-1) return 1;
return DFS(top+1,bot-1);
}
else if(S[top]<S[bot]) return 1;
else return 0;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i){
char ch;cin>>ch;S[i]=ch;
}
int top=1,bot=n,i=1;
while(top<bot){
if(S[top]==S[bot]){
if(DFS(top+1,bot-1)){//top较大
Id[top]=i;
++i;++top;
}
else{
Id[bot]=i;
++i;--bot;
}
}
else if(S[top]<S[bot]){
Id[top]=i;
++i;++top;
}
else{
Id[bot]=i;
++i;--bot;
}
}
Id[bot]=n;
top=1,bot=n;
for(int i=1;i<=n;++i){
// printf("top=%d,%d bot=%d,%d\n",top,Id[top],bot,Id[bot]);
if(Id[top]==i){
cout<<S[top];++top;
//printf("%c",S[top]);++top;
}
else{
cout<<S[bot];--bot;
//printf("%c",S[bot]);--bot;
}
if(i%80==0) cout<<"\n";
}
}
京公网安备 11010502036488号