开始一个小时的时候还是懵的，之后状态稍微好一点了，一共写了11题，如果一开始一个小时写快一点的话最后一题也应该写得出来
Problem A
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
勇士 haruhi 要铸造一个传说！
但是在这之前，他需要打败恶龙。
众所周知的是，恶龙的攻击力非常高，haruhi 作为一个攻击力只有 0 的家伙，需要去招募青蛙来攻打恶龙。
haruhi 到恶龙巢穴的路上有 n 个酒馆，每个酒馆里都有一些青蛙。(不要问青蛙为什么在酒馆里)
青蛙作为一种中立生物，对 haruhi 也是有敌意的，除非 haruhi 花钱招募它们，或者 haruhi已经招募的青蛙的攻击力比当前酒馆里青蛙的攻击力多或者相等，他才能安全地走出这个酒馆，抵达下一个地方。
haruhi 会按照 1 到 n 的顺序，走遍这些酒馆。
现在，haruhi 想要问你，他最少需要准备多少钱，才能招募到足够多的青蛙，打败恶龙。
其他设定如下：
1、haruhi 只能够选择要么招募整个酒馆的青蛙，要么一只都不要。
2、最后，青蛙的攻击力总和大于等于恶龙，那么，haruhi 就可以顺利的打败恶龙。
3、同一个酒馆里，青蛙的攻击力是一样的。
Input
第一行一个整数 T,代表 T 组数据。(T<=20)
首先每行两个数 n,k，分别代表酒馆的数量，和恶龙的攻击力。(n<=500,k<=109)
接下来有三行。
第一行 n 个数，代表每个酒馆里青蛙的数量。(1<=a[i]<=3000)
第二行 n 个数，代表每个酒馆里每只青蛙的攻击力。(1<=b[i]<=3000)
第三行 n 个数，代表招募到这个酒馆所有青蛙所需要付出的金币数。(1<=c[i]<=10)
Output
对于每组数据，输出一个数，代表 haruhi 需要花的最少钱数。
如果 haruhi 战胜不了恶龙，输出"chu ti zhe ying gai xue yi xia e long"。(不含引号)
Sample Input
1 3 9 2 2 3 3 4 1 5 8 1
Sample Output
13
dp[i][j]表示前i个酒馆花费为j时的最大攻击力
#include<bits/stdc++.h>
using namespace std;;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e3+100;
const int INF=0x7fffffff;
int n,k,w[maxn],c[maxn],dp[510][5010];
void init(){
rep(i,0,n) rep(j,0,n*10) dp[i][j]=-INF;
dp[1][c[1]]=w[1];
}
void solve(){
scanf("%d%d",&n,&k); int x;
rep(i,1,n) scanf("%d",&w[i]);
rep(i,1,n) scanf("%d",&x),w[i]*=x;
rep(i,1,n) scanf("%d",&c[i]);
init();
rep(i,2,n) for(int j=0;j<=n*10;++j){
if(dp[i-1][j]>=w[i]) dp[i][j]=max(dp[i][j],dp[i-1][j]);
dp[i][j+c[i]]=max(dp[i][j+c[i]],dp[i-1][j]+w[i]);
}
rep(i,0,n*10) if(dp[n][i]>=k) {printf("%d\n",i);return;}
printf("chu ti zhe ying gai xue yi xia e long\n");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem B
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
有的时候，题目和内容是没有一点关系的。
当然，作为一个有责任心的出题者，会把题目和名字紧紧联系在一起。
显然，小花不是一个有责任心的出题者。
由于他想尽早的完成出题任务，于是他把出题的流程抽象成了一棵树。
例如，当出完题目后，小花可以选择先写标程，或是先造数据。但找人验题，一定是在造完数据以后。
他现在正处在其中的某个阶段，你可以把所有的阶段都视为一个点。
烦人的 boss 又在催促他,并询问最快还有多久才能到第 x 个阶段。
所有的询问相互独立。
Input
第一行一个整数 T,代表 T 组数据。(T<=500)
接下来每行三个数 n，m，r。代表有 n 个阶段，m 个询问,小花现在正处在第 r 个阶段。(1<=n,m<=100000)
接下来 n-1 行，每行两个数，u,v,代表 v 阶段在 u 阶段之后。(1<=u,v<=n)
接下来一行有 m 个数，代表 boss 询问到第 x 个阶段还有多久。(1<=x<=n)
Output
对于每组数据，输出 m 个数，代表小花最快还有几步才能到要求的阶段。
如果小花已经完成了 boss 询问的那个阶段，那么对此询问输出 0。
如果无法确定小花是不是完成了那个阶段，输出-1。
如果询问的就是小花所在的阶段，输出 0。
每个询问后输出一个空格，每组数据后输出一个换行。
Sample Input
1 5 2 1 1 2 1 3 2 4 2 5 3 4
Sample Output
1 2
正图反图遍历一遍编个号
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n,m,r,rt;
struct edge{
int v,next;
}g1[maxn],g2[maxn];
int tot1,tot2,head1[maxn],head2[maxn],ans[maxn],vis[maxn];
void init(){
rep(i,1,n) head1[i]=0,head2[i]=0,vis[i]=0,ans[i]=-1;
tot1=tot2=1;
}
void add1(int u,int v){
g1[tot1] = {v,head1[u]}; head1[u] = tot1++;
}
void add2(int u,int v){
g2[tot2] = {v,head2[u]}; head2[u] = tot2++;
}
void dfs1(int x){
ans[x]=0;
for(int i=head2[x];i;i=g2[i].next){
int v=g2[i].v;
dfs1(v);
}
}
void dfs2(int x){
for(int i=head1[x];i;i=g1[i].next){
int v=g1[i].v;
if(ans[v]!=-1) ans[v]=min(ans[v],ans[x]+1);
else ans[v]=ans[x]+1;
dfs2(v);
}
}
void solve(){
scanf("%d%d%d",&n,&m,&r);
init();
rep(i,1,n-1){
int u,v;scanf("%d%d",&u,&v);
add1(u,v);add2(v,u);
}
dfs1(r);dfs2(r);
rep(i,1,m){
int q;scanf("%d",&q);
printf("%d ",ans[q]);
}
printf("\n");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem C
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
花园小学正在进行紧张刺激的运动会！每个班级都有一个独一无二的数字。
现在正是 10000 米短跑比赛的现场。许多班级的运动员们已经纷纷准备就绪。正等一声令下，开始比赛。10000 米短跑比赛有一个传统，就是每当一个运动员跑到终点时，都会大声喊出他的班级号，来显示一种荣耀。现在，给出 n 个数，代表通过终点的 n 个人所喊出的班级号，你需要统计有多少班级在这场比赛中参赛了正好 k 个人，计算出在这些班级中，获得第一名的选手是哪个班级的。输出他所在的班级号。
假设每一个参加比赛的人都通过了终点。
Input
每组数据第一行，n，k。代表有 n 个人，要求保留 k 个人的班。(n,k<=1000000)
接下来一行 n 个数，依次代表选手通过终点所喊出的班级号（a[1]代表第一个通过终点的选手喊出的班级号，依次类推）。 (a[i]<=1000000)
处理到文件结束。
Output
每行一个数。
若没有班级通过 k 人，输出-1。
Sample Input
5 2 4 2 3 2 3
Sample Output
2
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,k,a[maxn],c[maxn];
void solve(){
rep(i,1,maxn-10) a[i]=0;
rep(i,1,n){
scanf("%d",&c[i]);
a[c[i]]++;
}
rep(i,1,n) if(a[c[i]]==k) {printf("%d\n",c[i]);return;}
printf("-1\n");
}
int main(){
while(~scanf("%d%d",&n,&k)){
solve();
}
}
Problem D
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
大三的 Rabbit 已经开始考研了，她需要参加数学、英语、政治、专业课四门考试，四门课的满分分别是 150,100,100,150。
不过她了解到考研与普通考试不同，要想被录取不仅要总分到达国家线(320分)，而且单科成绩也必须到达单科线。
这里每门课的单科线为这门课满分的 60%。
过了几个月，考研成绩出来了，Rabbit 得到了班上所有 N 位同学的成绩，现在她想知道哪些同学能被录取，并根据她们的总分从大到小排序(若总分相同，则按照名字的字典序从小到大排序)。
注：到达指的是大于等于，数据保证学生名字是只由小写字母和大写字母组成的不同字符串，且至少有一位同学能被录取。
Input
输入数据第一行为 T，表示数据组数。(1<=T<=20)
每组数据第一行为 N，表示学生人数。(1<=N<=100)
接下来 N 行,每行首先是一个字符串 S，表示第 i 个学生的名字，接下来四个整数 M,E,P,Z，分别表示该学生的数学成绩，英语成绩，政治成绩，专业课成绩。(1<=|S|<=10，1<=E,P<=100，1<=M,Z<=150)
Output
对于每组数据输出若干行，每行输出被录取的学生按照成绩排序后的名字和总分，用空格隔开。
Sample Input
1 3 Bob 105 70 65 110 John 135 55 70 120 Tom 100 75 70 120
Sample Output
Tom 365 Bob 350
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,m;
char str[12];
struct node{
string name;
int a,b,c,d;
int tot;
}p[110];
int cmp(node a,node b){
if(a.tot==b.tot) return a.name<b.name;
return a.tot>b.tot;
}
void solve(){
scanf("%d",&n);
rep(i,1,n){
scanf("%s%d%d%d%d",str,&p[i].a,&p[i].b,&p[i].c,&p[i].d);
p[i].name=str;p[i].tot=p[i].a+p[i].b+p[i].c+p[i].d;
}
sort(p+1,p+1+n,cmp);
rep(i,1,n) if(p[i].tot>=320&&p[i].a>=90&&p[i].b>=60&&p[i].c>=60&&p[i].d>=90){
cout<<p[i].name;
printf(" %d\n",p[i].tot);
}
}
int main(){
int T;cin>>T;
while(T--){
solve();
}
}
Problem E
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
Rabbit 得到了一张秘密纸条，上面是由密密麻麻的小写字母组成的字符串。
已知，字符 c 与字符'z'-c+'a'是相反的。(即‘a’与‘z’，‘b’与‘y’......)
现在规定对称相反子串的定义为该子串从中间到两边对应位置的字符都是相反的。
例如给定字符串"azza",其对称相反子串有“a”，“z”，“az”，“azz”,"zza","za"。
Rabbit 想知道最长的对称相反子串的长度是多少？
Input
输入数据第一行为 T，表示数据组数。(1<=T<=10)
每组数据占一行，为字符串 S。(1<=|S|<=1000)
Output
对于每组数据输出一个整数，代表最长的对称相反子串的长度，占一行。
Sample Input
2 kadwxdwz abcdevdcba
Sample Output
7 2
长度1000，暴力
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
char str[1100];
int len;
int check(int pos){
int p1=pos,p2=pos,p3=pos,p4=pos+1,flag1=1,flag2=1;
while(1){
if(flag1){
if(p1==p2||str[p1]=='z'-str[p2]+'a'||str[p2]=='z'-str[p1]+'a') p1--,p2++;
else flag1=0;
}
if(flag2){
if(str[p3]=='z'-str[p4]+'a'||str[p4]=='z'-str[p3]+'a') p3--,p4++;
else flag2=0;
}
if(p1<1||p2>len) flag1=0;
if(p3<1||p4>len) flag2=0;
if(flag1==0&&flag2==0) break;
}
p1++;p2--;
p3++;p4--;
return max(p2-p1+1,p4-p3+1);
}
void solve(){
scanf("%s",str+1);
len=strlen(str+1);
int ans=0;
rep(i,1,len) ans=max(ans,check(i));
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem F
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
Rabbit 考研结束后相约与同学去郊游。他们想尽快到达目的地，但是有的人
走得快有的人走得慢，这让 Rabbit 很苦恼。
不过好在 Rabbit 能够对走得比较慢的人施展魔法。
假设第 i 个人的步行速度为 vi 米/分钟，对他施展魔法之后能让他的速度变为wi 米/分钟。
现在 Rabbit 想知道他们最快能在第几分钟全部达到目的地。
注：一分钟只能施展一次魔法，且持续时间为一分钟。
Input
输入数据第一行为 T，表示数据组数。(1<=T<=10)
每组数据第一行为两个整数 N，S，分别表示学生总数和距离目的地的距离。
(1<=N,S<=10^5)
接下来 N 行，第 i 行有两个整数 vi，wi。(1<=vi<=wi<=10^5)
Output
对于每组数据输出一个整数，表示最快能在第几分钟全部达到目的地，占一行。
Sample Input
1 3 9 5 10 2 4 3 7
Sample Output
3
二分答案暴力判断
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n,s,ans;
int v[maxn],w[maxn];
int check(int ti){
int res=0;
int t=0;
rep(i,1,n) if(ti*v[i]<s){
if(w[i]<=v[i]) return 0;
res+=(s-ti*v[i])/(w[i]-v[i]);
if((s-ti*v[i])%(w[i]-v[i])) res++;
}
return res<=ti;
}
void solve(){
scanf("%d%d",&n,&s);
rep(i,1,n) scanf("%d%d",&v[i],&w[i]);
int l=1,r=maxn,mid=(l+r)>>1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans = mid;
else l = mid+1;
}
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--){
solve();
}
}
Problem G
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
小明在玩一个战略游戏。他现在的任务是找到敌方的军队在什么地方。他已经知道敌方的军队可能在的几个区域和每个区域敌方的军队可能存在的概率，且敌方的军队只可能存在于这些区域中的某一个区域当中。他拥有一个科技：可以同时扫描若干个区域并花费区域个数的金钱。但游戏有一定的限制，小明必须将这些区域分成 k 组，且只能对 k 组的区域依次进行一次扫描。现在小明想知道怎么样的划分区域的策略可以使得找到敌军时花费的金钱数的数学期望最小。
Input
输入第一行是一个正整数 T(T<=10），表示数据组数。
接 下 来 对 于 每 组 数 据 ， 第 一 行 给 出 两 个 正 整 数 n(1<=n<=100) 和k(1<=k<=n<=100），分别表示区域个数和划分组数。第二行给出 n 个不超过 100的正整数，依次代表每个区域的概率（单位：%），其中保证所有区域的概率相加等于 100%。
Output
对于每组数据，输出一个实数，表示花费金钱数的数学期望的最小值，保留3 位小数。
Sample Input
2 5 2 30 5 10 30 25 5 5 30 5 10 30 25
Sample Output
3.200 2.300
Hint
第一个样例中先同时扫描第一个和第四个区域，再扫描第二、三、五个区域，
从而花费的金钱数的数学期望为 2*(0.3+0.3)+(3+2)*(0.05+0.1+0.25)=3.200
对于概率降序排，然后维护dp[i][j]表示前i个概率分为j个区间的最大值
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,k;
double a[110],dp[110][110];
void solve(){
scanf("%d%d",&n,&k);
memset(dp,0x7f7f7f7f,sizeof(dp));
dp[0][0]=0.0;
rep(i,1,n) scanf("%lf",&a[i]),a[i]/=100.0;
sort(a+1,a+1+n,greater<double>());
rep(i,2,n) a[i]+=a[i-1];
rep(i,1,n) rep(j,1,min(i,k)) rep(e,0,i){
double res=1.0*i*(a[i]-a[e]);
dp[i][j]=min(dp[i][j],dp[e][j-1]+res);
}
//rep(i,1,n) rep(j,1,k) printf("%.3lf\n",dp[i][j]);
printf("%.3lf\n",dp[n][k]);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem H
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
小明的算法竞赛水平很高，他经常参加网上的比赛。
比赛的规则是这样的：要在规定时间内解决 n 道题，解决时间越晚失去的分数就越多。
当然如果有错误提交还会扣额外的分数。为了简化题目，我们假设小明所有题目都可以一遍 AC。
小明实在是太强了，以致于他看完所有题目就都会做了。剩下的就是把它们写出来的问题。小明掐指一算，算出了写每道题需要的时间 Ti，以及每道题每分钟会失去的分数 Ai。也就是说，如果他在 x 分钟时完成这道题，他将失去 x * Ai的分数。
请合理安排做题顺序，使得当小明做完比赛时，失去的分数尽可能少。
Input
第一行给出一个正整数 T（T<=10），表示数据组数。
对于每组数据，第一行一个正整数 n，表示这场比赛的题目数。第二行 n 个整数，表示做每道题需要的时间 Ti。第三行 n 个整数，表示每题每分钟失去的分数 Ai。
其中：0<n<=100000,0<Ti,Ai<=10000
Output
对于每组数据，输出一个整数，表示最少失去的分数。
Sample Input
1 3 10 10 20 1 2 3
Sample Output
150
a/t降序排后暴力模拟
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n;
struct node{
int t,a;
double d;
}p[maxn];
int cmp(node a,node b){
return a.d>b.d;
}
void solve(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&p[i].t);
rep(i,1,n){
scanf("%d",&p[i].a);
p[i].d=1.0*p[i].a/p[i].t;
}
sort(p+1,p+1+n,cmp);
ll ans=0,ti=0;
rep(i,1,n){
ti+=p[i].t;
ans+=ti*1ll*p[i].a;
}
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
while(T--){
solve();
}
}
Problem I
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
小明来到礼品店准备给女朋友挑选礼物。店员给小明展示了 n 个商品，这 n个物品排成一排。并表示如果小明购买连续的 c 个商品会有特别大的优惠。小明接受了店员的提议，决定购买连续的 c 个商品。这 n 个商品每个都有一个美观度ai。小明不希望自己送的礼品美观度都太低，所以希望买到的 c 个商品的美观度都能比 k 大。小明想知道有多少种购买方案能够达到这个要求。
Input
第一行给出一个正整数 T(T<=10)，表示数据组数。
对于每组数据，第一行给出三个整数 n(1<=n<=200000)，k(0<=k<=1e9)和c(1<=c<=n)。第二行给出 n 个正整数 ai(0<=ai<=1e9)，依次表示 n 个商品的美观度。
Output
对于每组数据，输出一个整数表示能够达到要求的购买方案数，占一行。
Sample Input
3 4 3 3 2 3 1 1 1 1 1 2 4 0 3 2 3 1 1
Sample Output
0 1 2
简单模拟
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,k,c,a[maxn];
void solve(){
scanf("%d%d%d",&n,&k,&c);
ll ans=0;
rep(i,0,n) a[i]=0;
rep(i,1,n){
int x;scanf("%d",&x);
if(x>k){
if(a[i-1]) a[i]=a[i-1]+1;
else a[i]=1;
}
else if(x<=k){
if(a[i-1]){
ans+=max(0,a[i-1]-c+1);
}
}
if(i==n&&a[i]) ans+=max(0,a[i]-c+1);
}
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem J
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
下面是传说中的赌徒必胜策略：
如果输的话按上把下注额翻倍下注，这样即使连败，因为总有获胜的时候，只要赢一次就可以把输的钱全部赢回，当钱不足以按策略下注时，就把拥有的所有钱都下注。
现在两个赌狗 A，B 都学到了这个方法，他们决定带着钱找对方练一练，他们每次都进行一次胜率各为 50%的赌局，赌局的大小由上局输的人决定（第一次赌局的大小为 1 元），一直到其中一个人的钱输光为止。请你告诉这两个赌狗.他们赢光对方钱的概率为多少。
Input
第一行一个正整数 T，表示共有 T(T<=100)组数据
接下来每一行两个正整数 a,b(1<=a,b<=100),分别表示 A 和 B 拥有的钱
Output
输出一个实数，表示 A 获胜的概率，保留三位小数。
Sample Input
1 1 1
Sample Output
0.500
显然答案是a/(a+b)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int main(){
int T;cin>>T;
while(T--){
double a,b;cin>>a>>b;
printf("%.3lf\n",a/(a+b));
}
}
Problem K
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
平面上有 n 个点（任意两点的横坐标与纵坐标都不会相同），每个点向 x 轴和 y 轴做垂线分别形成两个交点，两个交点和该点以及坐标原点构成一个矩形，并覆盖矩形内的点（在边缘上的点不算被覆盖），请输出平面上所有一次也没有被覆盖过的点。
Input
第一行一个正整数 T(T<=5)，表示共有 T 组数据。
每组数据的第一行一个正整数数 n(1<=n<= 200000),表示平面上有 n 个点。
接下来 n 行每行两个正整数 x,y(1<=x,y<= 1e9)表示一个点的横纵坐标。
Output
按 x 轴坐标从小到大输出所有符合条件的点。
Sample Input
1 5 8 1 17 5 9 6 12 11 13 7
Sample Output
12 11 13 7 17 5
二维偏序
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,ans[maxn],pos;
struct node{
int x,y;
}p[maxn];
int cmp(node a,node b){
return a.x<b.x;
}
void solve(){
scanf("%d",&n);
rep(i,1,n) scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+1+n,cmp);
int maxx=0;
pos=0;
dep(i,n,1){
if(p[i].y>maxx){
ans[++pos]=i;
maxx=p[i].y;
}
}
dep(i,pos,1) printf("%d %d\n",p[ans[i]].x,p[ans[i]].y);
}
int main(){
int T;cin>>T;
while(T--){
solve();
}
}
Problem L
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Problem Description
世界上的大佬太多了，菜鸡们纷纷自闭并来到心理诊所寻求治疗，心理诊所的每一个医生有不同的开始上班时间，能力 a 和收费 c，能力为 a 的医生可以治好自闭程度小于或等于 a 的菜鸡。菜鸡们都很穷，所以他们只想要能治好他们的最便宜的医生，请你告诉他们当前能治好他们病的最便宜的医生的价格。（假设治疗在瞬间完成，同一个医生可以连续接待任意个客人）
Input
第一行一个正整数 T(T<=5),表示数据的组数
每组数据第一行一个正整数 n(n <= 10^5)，表示接下来有 n 行。
接下来 n 行中，若第一个数为 0，则接下来两个正整数 a,c 表示有一个能力为 a，收费为 c 的医生上班了。若第一个数为 1，则接下来有一个正整数 b，表示有一个自闭程度为 b 的菜鸡来寻求治疗(1<=a,b,c <= 10^9)。
Output
对每个寻求治疗的菜鸡，输出一个整数表示治疗需要的花费，如果没有医生能治好他，输出“-1”。
Sample Input
1 8 1 19 0 17 5 0 1 6 1 12 1 15 0 5 7 0 3 9 1 3
Sample Output
-1 5 5 5
先离散一下能力值，再线段树维护一下区间最小值
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R
#define delf int mid=(L+R)>>1
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
const int INF=0x7fffffff;
int n;
int s[maxn<<2],ls[maxn];
struct node{
int op,nl,c;
}p[maxn];
void pushup(int rt){
s[rt]=min(s[rt<<1],s[rt<<1|1]);
}
void build(int rt,int L,int R){
if(L==R) {s[rt]=INF;return;}
delf; build(lson); build(rson);
pushup(rt);
}
void update(int rt,int L,int R,int pos,int val){
if(L==R){s[rt]=min(s[rt],val);return;} delf;
if(pos<=mid) update(lson,pos,val);
else update(rson,pos,val);
pushup(rt);
}
int query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r) return s[rt];
delf;
int minx=INF;
if(l<=mid) minx=min(minx,query(lson,l,r));
if(r>mid) minx=min(minx,query(rson,l,r));
return minx;
}
void solve(){
scanf("%d",&n);
rep(i,0,n-1){
scanf("%d%d",&p[i].op,&p[i].nl);
if(p[i].op==0) scanf("%d",&p[i].c);
ls[i]=p[i].nl;
}
sort(ls,ls+n);
int size=unique(ls,ls+n)-ls;
rep(i,0,n-1) p[i].nl=lower_bound(ls,ls+size,p[i].nl)-ls+1;
build(1,1,maxn-100);
rep(i,0,n-1){
if(p[i].op){
int ans=query(1,1,maxn-100,p[i].nl,maxn-100);
if(ans==INF) printf("-1\n");
else printf("%d\n",ans);
}
else{
update(1,1,maxn-100,p[i].nl,p[i].c);
}
}
}
int main(){
int T;cin>>T;
while(T--)solve();
}
