MC0479四大名著-红楼签到、MC0480宝物排序、MC0481丫鬟的月例银、MC0482院落管理

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 3import 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 N5*100010; static int a[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer stnew StringTokenizer(br.readLine()); int nInteger.parseInt(st.nextToken()),qInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 0; i n; i) { a[i1]Integer.parseInt(st.nextToken()); } for (int i 0; i q; i) { stnew StringTokenizer(br.readLine()); int optInteger.parseInt(st.nextToken()),indInteger.parseInt(st.nextToken()),vInteger.parseInt(st.nextToken()); if(opt1){ a[ind]v; }else{ a[ind]-v; } } StringBuilder stringBuildernew StringBuilder(); for (int i 1; i n; i) { stringBuilder.append(a[i]); if(in)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复制输出3import 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 N2*100010; static int a[]new int[N]; static SetInteger setnew TreeSet(); public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); String g[]br.readLine().split( ); int nInteger.parseInt(g[0]),kInteger.parseInt(g[1]); gbr.readLine().split( ); for (int i 0; i n; i) { a[i1]Integer.parseInt(g[i]); set.add(a[i1]); } int id0; for(int i:set){ id; if(idk){ 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复制输出500000000import 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 N5*100010; static int a[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer stnew StringTokenizer(br.readLine()); int tInteger.parseInt(st.nextToken()); for (int i 0; i t; i) { stnew StringTokenizer(br.readLine()); int nInteger.parseInt(st.nextToken()); long mLong.parseLong(st.nextToken()); stnew StringTokenizer(br.readLine()); long r(int)1e91;//这个必须要加1 因为一定要保证能找到d for (int j 0; j n; j) { a[j]Integer.parseInt(st.nextToken()); } long l1; while(lr){ long d(lr)1; if(check(d,n,m)){ rd; }else{ ld1; } } bw.write(l\n); bw.flush(); } br.close(); bw.close(); } static boolean check(long d,int n,long m){ long sum0; for (int i 0; i n; i) { suma[i]/d; } if(summ){ 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 YESimport 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 N5*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 ListInteger[] adjnew List[N];//邻接表 public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer stnew StringTokenizer(br.readLine()); int tInteger.parseInt(st.nextToken()); for (int i 0; i t; i) { stnew StringTokenizer(br.readLine()); int nInteger.parseInt(st.nextToken()); long kLong.parseLong(st.nextToken()); stnew 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) { stnew StringTokenizer(br.readLine()); int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); //无向边 添加两条 adj[a].add(b); adj[b].add(a); } //我们从叶子结点开始考虑 从根节点开始考虑情况太复杂 //那么我们怎么找到叶子节点呢 我们可以先找到树的前序遍历结果 将其存入链表中 //然后我们可以倒着来遍历 StackInteger stacknew Stack(); ListInteger frontResultnew ArrayList(); stack.add(1); for (int j 1; j n; j) { p[j]-1; } p[1]0; while(!stack.isEmpty()){ int topstack.pop(); frontResult.add(top); for(int son:adj[top]){ if(sonp[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 ftrue; for (int j frontResult.size()-1; j 0; j--) {//这里一定要使用ArrayList 效率比较高 int xfrontResult.get(j); ListInteger mustnew ArrayList();//存必须要和我连的子节点 ListInteger mayconnew ArrayList();//存可以和我连的子节点 for(int son:adj[x]){ if(sonp[x])continue; //一定要是if-else if(!used[son])must.add(sum[son]); else if(may[son])maycon.add(sum[son]); } if(must.size()2){ //比如k10 // p // s112 s211 s315 (p的各个子节点对应sum) 每个都需要依赖父节点 这不可能 ffalse; 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]){//注意此句 我不能独立 而且我也连不上去 ffalse;break; } } if(ftrue used[1]){ bw.write(YES\n); }else{ bw.write(NO\n); } } br.close(); bw.flush(); bw.close(); } }