D. Nene and the Mex Operator

本文主要是介绍D. Nene and the Mex Operator，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

 解题思路

• 若选定一个区间，则可以构造成值全为
• 构造方如下：
• 先将区间全变为0
• （若区间有0且不全为0两次（全变为一个值后再全变为0），若没有0则一次，若已经全为0则0次）
• 保留r为0，依次递归构造，每次保留左端值
• 则构造出区间值为，再一次变为全
• 例：0 0 0 0->1 0 0 0->2 2 0 0->2 0 0 0-> 2 1 0 0->3 3 3 0->3 0 0 0->……->3 2 1 0->4 4 4 4 
• 预处理出需要构造的区间
• 即

import java.io.*;
import java.math.BigInteger;
import java.util.*;//implements Runnable
public class Main {static long md=(long)1e9+7;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static int N=200010;static int n=0;static int m=0;staticclass M{int x,y;public M(int u,int v){x=u;y=v;}}static Vector<M> stp;static long[] a;static void get(int l,int r){if(l==r){if(a[l]!=0)stp.add(new M(l,r));stp.add(new M(l,r));a[l]=1;return;}boolean zero=false;boolean ok=true;for(int i=l;i<=r;++i){if(a[i]==0)zero=true;else ok=false;}if(!ok){if(zero)stp.add(new M(l,r));stp.add(new M(l,r));for(int i=l;i<=r;++i)a[i]=0;}for(int i=l;i<r;++i)get(i,r-1);stp.add(new M(l,r));for(int i=l;i<=r;++i)a[i]=r-l+1;}static void solve() throws Exception{AReader input=new AReader();
//        String fileName="";
//		Scanner input=new Scanner(new FileReader(fileName));//        BufferedReader input = new BufferedReader(new FileReader(fileName));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));String al="abcdefghijklmnopqrstuvwxyz";char[] ac=al.toCharArray();n=input.nextInt();a=new long[n+1];for(int i=1;i<=n;++i)a[i]=input.nextLong();long[] sum=new long[n+1];int[] len=new int[n+1];for(int i=1;i<=n;++i){sum[i]=sum[i-1]+a[i];for(int j=1;j<=i;++j){if(sum[i]<sum[i-j]+(long)j*j){len[i]=j;sum[i]=sum[i-j]+(long)j*j;}}}stp=new Vector<>();out.print(sum[n]+" ");int r=n;while(r>0){if(len[r]==0){r--;continue;}int l=r-len[r]+1;get(l,r);r=l-1;}out.println(stp.size());for(M now:stp){out.println(now.x+" "+now.y);}out.flush();out.close();}public static void main(String[] args) throws Exception{solve();}//	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Tx2(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}staticclass AReader{BufferedReader bf;StringTokenizer st;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}}
}

这篇关于D. Nene and the Mex Operator的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---