MC0479四大名著-红楼签到
前言：这套命题将以《红楼梦》为经纬，和大家一起完成跨时空的探险之旅。
小码妹来到红楼世界，看到贾府管家王熙凤需要管理乌进孝进贡的物品清单。给定一个长度为nn的整数序列a1∼ana1∼an（对应乌进孝进贡清单中的各项物品数量），现在有qq次操作，每次操作有两种类型：
1. 赏赐增加1 i v：将整数序列第i个位置的数值加上v。
2. 赏赐减少2 i v：将整数序列第i个位置的数值减去v。
现在问小码妹，经过qq次操作后，该整数序列变成怎样了？输出操作后的整数序列。
格式
输入格式：
第一行两个整数n,q(1≤n≤5×105,1≤q≤5×105)n,q(1≤n≤5×105,1≤q≤5×105)。
第二行nn个整数a1∼an(1≤ai≤1000)a1∼an(1≤ai≤1000)。
接下来qq行，每行三个整数opt,i,v(opt∈{1,2},1≤i≤n,1≤v≤1000)opt,i,v(opt∈{1,2},1≤i≤n,1≤v≤1000)，表示对应操作。
输出格式：
一行nn个整数，表示序列a1∼ana1∼an操作后的结果。
样例 1
输入：
3 2 1 2 3 1 1 5 2 2 10
复制
输出：
6 -8 3
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N=5*100010; static int a[]=new int[N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st=new StringTokenizer(br.readLine()); int n=Integer.parseInt(st.nextToken()),q=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { a[i+1]=Integer.parseInt(st.nextToken()); } for (int i = 0; i < q; i++) { st=new StringTokenizer(br.readLine()); int opt=Integer.parseInt(st.nextToken()),ind=Integer.parseInt(st.nextToken()),v=Integer.parseInt(st.nextToken()); if(opt==1){ a[ind]+=v; }else{ a[ind]-=v; } } StringBuilder stringBuilder=new StringBuilder(); for (int i = 1; i <= n; i++) { stringBuilder.append(a[i]); if(i<n)stringBuilder.append(" "); } bw.write(stringBuilder.toString().trim()); bw.flush(); } }MC0480宝物排序
迎春探春两姐妹得到一个任务，要清点大观园中的奇珍异宝。需要整理出一份宝物清单，记录每件宝物的珍贵程度评分（评分越高越珍贵）。现需找出其中第k珍贵的宝物。
即：给到一个长度为nn的宝物珍贵程度评分序列a1∼ana1∼an（每个评分对应一件具体宝物），现在问你该序列的“k珍贵值”是多少？
定义“k珍贵值”：
1. 必须存在于宝物序列中。
2. 序列中恰好存在k-1种不同的评分值小于该“k珍贵值”。
如果存在“k珍贵值”，输出这个数值，否则输出-1。
格式
输入格式：
第一行两个整数n,k(1≤n≤2×105,1≤k≤n)n,k(1≤n≤2×105,1≤k≤n)。
第二行nn个整数a1∼an(1≤ai≤109)a1∼an(1≤ai≤109)。
输出格式：
一行一个整数，表示答案。
样例 1
输入：
3 2 1 1 3
复制
输出：
3
复制
样例 2
输入：
3 3 1 1 3
复制
输出：
-1
复制
样例 3
输入：
8 3 1 1 1 2 2 3 3 4
复制
输出：
3
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N=2*100010; static int a[]=new int[N]; static Set<Integer> set=new TreeSet<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]),k=Integer.parseInt(g[1]); g=br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i+1]=Integer.parseInt(g[i]); set.add(a[i+1]); } int id=0; for(int i:set){ id++; if(id==k){ System.out.println(i); return; } } System.out.println(-1); } }MC0481丫鬟的月例银
年终结算时，贾母发现各房主子丫鬟的月例银总额太高了。为了削减开支，需要进行调整。现在假设荣国府一共有nn个丫鬟，她们的月例银排成正整数序列为a1∼ana1∼an。现在削减开支的目标，是要让这nn个数字之和不超过mm。
为了实现这一目标，小码妹可以钦定一个正整数DD，使得所有的aiai变成⌊aiD⌋⌊Dai⌋，现在问，要实现这一目标，DD最小可以是多少（当然不能小于11）？
格式
输入格式：
第一行一个整数T(1≤T≤5×105)T(1≤T≤5×105)，表示测试数据组数，对于每组测试数据：
第一行两个整数n,m(1≤n≤5×105,1≤m≤1012)n,m(1≤n≤5×105,1≤m≤1012)。
第二行nn个整数a1∼an(1≤ai≤109)a1∼an(1≤ai≤109)。
数据保证 ∑n≤5×105∑n≤5×105。
输出格式：
对于每组测试数据，一行一个整数，表示答案。
样例 1
输入：
3 5 10 10 10 4 10 6 5 10 1 1 1 1 1 5 10 2 2 3 2 2
复制
输出：
4 1 2
复制
样例 2
输入：
1 1 1 999999999
复制
输出：
500000000
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N=5*100010; static int a[]=new int[N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st=new StringTokenizer(br.readLine()); int t=Integer.parseInt(st.nextToken()); for (int i = 0; i < t; i++) { st=new StringTokenizer(br.readLine()); int n=Integer.parseInt(st.nextToken()); long m=Long.parseLong(st.nextToken()); st=new StringTokenizer(br.readLine()); long r=(int)1e9+1;//这个必须要加1 因为一定要保证能找到d for (int j = 0; j < n; j++) { a[j]=Integer.parseInt(st.nextToken()); } long l=1; while(l<r){ long d=(l+r)>>1; if(check(d,n,m)){ r=d; }else{ l=d+1; } } bw.write(l+"\n"); bw.flush(); } br.close(); bw.close(); } static boolean check(long d,int n,long m){ long sum=0; for (int i = 0; i < n; i++) { sum+=a[i]/d; } if(sum<=m){ return true; }else { return false; } } }MC0482院落管理
元宵佳节将近，袭人与鸳鸯需将园中nn处院落进行划分。具体而言，nn处院落构成树状布局（各院通过甬道相连）。各院落看成树上的点，编号为1∼n1∼n，其中编号为ii的点的点权为aiai。
问现在能否划分为若干路径，将整个区域所有院落正好完整覆盖，要求：
1. 全覆盖：每处院落必属某条路径。
2. 无交集：任意两条路径不含相同院落。
3. 成本控制：每条路径包含院落的点权之和≤k。
如果可以，输出YES，否则输出NO。
注意，一条路径定义为从一个点走到另一个点在经过最少数量的边的前提下构成的点和边的集合。特殊的， 一个单点也算一条路径。
格式
输入格式：
第一行一个整数T(1≤T≤5×105)T(1≤T≤5×105)，表示测试数据组数。
对于每组测试数据：
第一行两个整数n,k(1≤n≤5×105,−109≤k≤109)n,k(1≤n≤5×105,−109≤k≤109)。
第二行nn个整数a1∼an(−2000≤ai≤2000)a1∼an(−2000≤ai≤2000)。
接下来n−1n−1行，每行两个整数u,v(1≤u,v≤n)u,v(1≤u,v≤n)，表示点uu和点vv之间有一条边。
其中，∑n≤5×105∑n≤5×105。
输出格式：
对于每组测试数据：
输出一行一个字符串YES或者NO。
样例 1
输入：
2 5 1 5 -3 2 1 -1 1 2 1 3 1 4 2 5 5 1 5 -3 1 1 -1 1 2 1 3 1 4 2 5
复制
输出：
NO YES
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N=5*100010; static int a[]=new int[N]; static int p[]=new int[N];//存父节点 static boolean used[]=new boolean[N];//存该子树是否可以完全封闭 也就是可以不依赖父节点 static boolean may[]=new boolean[N];//存是否i可以和父节点连接 i可以独立也可以不独立 static int sum[]=new int[N];//存该子树贪心可达的最小权重 static List<Integer>[] adj=new List[N];//邻接表 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st=new StringTokenizer(br.readLine()); int t=Integer.parseInt(st.nextToken()); for (int i = 0; i < t; i++) { st=new StringTokenizer(br.readLine()); int n=Integer.parseInt(st.nextToken()); long k=Long.parseLong(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int j = 1; j <= n; j++) { a[j]=Integer.parseInt(st.nextToken()); } for (int j = 1; j <= n; j++) { adj[j]=new ArrayList<>();//新建链表 } for (int j = 1; j < n; j++) { st=new StringTokenizer(br.readLine()); int a=Integer.parseInt(st.nextToken()),b=Integer.parseInt(st.nextToken()); //无向边 添加两条 adj[a].add(b); adj[b].add(a); } //我们从叶子结点开始考虑 从根节点开始考虑情况太复杂 //那么我们怎么找到叶子节点呢 我们可以先找到树的前序遍历结果 将其存入链表中 //然后我们可以倒着来遍历 Stack<Integer> stack=new Stack<>(); List<Integer> frontResult=new ArrayList<>(); stack.add(1); for (int j = 1; j <= n; j++) { p[j]=-1; } p[1]=0; while(!stack.isEmpty()){ int top=stack.pop(); frontResult.add(top); for(int son:adj[top]){ if(son==p[top])continue; stack.add(son); p[son]=top; } } for (int j = 1; j <=n; j++) {//注意初始化 used[j]=false; sum[j]=0; may[j]=false; } boolean f=true; for (int j = frontResult.size()-1; j >= 0; j--) {//这里一定要使用ArrayList 效率比较高 int x=frontResult.get(j); List<Integer> must=new ArrayList<>();//存必须要和我连的子节点 List<Integer> maycon=new ArrayList<>();//存可以和我连的子节点 for(int son:adj[x]){ if(son==p[x])continue; //一定要是if-else if(!used[son])must.add(sum[son]); else if(may[son])maycon.add(sum[son]); } if(must.size()>2){ //比如k=10 // p // s1=12 s2=11 s3=15 (p的各个子节点对应sum) 每个都需要依赖父节点 这不可能 f=false; break; } Collections.sort(maycon);//将可能连接的进行排序 方便找到最小的那几个 //下面相当于在维护used和may和sum if(must.isEmpty()){ if(a[x]<=k)used[x]=true; else if(!maycon.isEmpty() && a[x]+maycon.get(0)<=k)used[x]=true; else if(maycon.size()>=2 && a[x]+maycon.get(0)+maycon.get(1)<=k ){ used[x]=true; } sum[x]=a[x]; may[x]=true; if(!maycon.isEmpty() && maycon.get(0)<0){ //可以和父节点有关系 贪心的加一个负数 这样选更有利 sum[x]+=maycon.get(0); } }else if(must.size()==1){ if(a[x]+must.get(0)<=k)used[x]=true; else if(!maycon.isEmpty() && a[x]+must.get(0)+maycon.get(0)<=k)used[x]=true; may[x]=true; sum[x]=a[x]+must.get(0); }else{//must.size()==2 if(a[x]+must.get(0)+must.get(1)<=k)used[x]=true; } if(!used[x] && !may[x]){//注意此句 我不能独立 而且我也连不上去 f=false;break; } } if(f==true && used[1]){ bw.write("YES\n"); }else{ bw.write("NO\n"); } } br.close(); bw.flush(); bw.close(); } }
