求今日头条100%AC的代码

//看完题目10分钟就A出来了，结果载在第二题上 import java.util.Arrays; import java.util.Scanner; public class Main5 { //先把数组排序  数相差大于10为界限 分成多个区 //每个区有三总情况：区的数量%3==0、1、2 //等于0的区不用加题目 //等于1的区加2个题目。x1：%3等于1的区的数量 //等于2的区加1个题目。x2：%3等于2的区的数量 //最后结果=x1*2+x2*1 public static int f(int[] arr){ Arrays.sort(arr); int n = arr.length; int j=1; int x1=0;//%3等于1的区的数量 int x2=0;//%3等于2的区的数量 for (int i = 0; i < n-1; i++) { if(arr[i+1]-arr[i]<=10){ j++;//计算每个区的数量 }else{ if(j%3==2){ x2++; } if(j%3==1){ x1++; } j=1; } } if(j%3==2){ x2++; } if(j%3==1){ x1++; } return x1*2+x2*1; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n  = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i]=sc.nextInt(); } System.out.println(f(arr)); } }

异或那道题可以把每个数的二进制位求出来，用一个字典树维护，然后遍历每一个数按位贪心，比如这一位m是1，遍历的这个数这一位是0，那么和他异或的数就必须是1，如果这一位m是0，要大于m的话异或和的这一位可以是1也可以是零，ans加上之前维护的二进制位加上使这一位为1的数在字典树中查询有多少个数满足这个前缀的条件，然后在令这一位的异或和为0，继续向下遍历，最后的答案除以2.

import java.util.*; public class Main1 { public static void main(String args[]) { Scanner in = new Scanner(System.in); while(in.hasNextInt()) { int n = in.nextInt(); int[] nums=new int[n]; for(int i=0;i<n;i++){ nums[i]=in.nextInt(); } Arrays.sort(nums); int ret= 0; int front = nums[0]; int index=0; for(int i=1;i<n;i++){ int val = nums[i]; if(index==2){ front=val; index=0; }else{ index=(index+1)%3; if((val-front)<=10){ front=val; }else{ ret++; front=front+10; i--; } } } ret+=(3-index-1); System.out.println(ret); } in.close(); } } 第一题 排序+贪心 （每三个一组） AC 第二题 没思路！暴力30%。

//#pragma comment(linker, "/STACK:1024000000,1024000000") #include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <string> #include <set> #include <vector> using namespace std; #define pr(x) cout << #x << " = " << x << " " #define prln(x) cout << #x << " = " << x << endl const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7; typedef long long LL; void fwtXor(LL* a, int len) { if(len == 1) return; int h = len >> 1; fwtXor(a, h); fwtXor(a + h, h); for(int i = 0; i < h; ++i) { LL x1 = a[i]; LL x2 = a[i + h]; a[i] = (x1 + x2); a[i + h] = (x1 - x2); } } void ifwtXor(LL* a, int len) { if(len == 1) return; int h = len >> 1; for(int i = 0; i < h; ++i) { // y1=x1+x2 // y2=x1-x2 LL y1 = a[i]; LL y2 = a[i + h]; a[i] = (y1 + y2) / 2; a[i + h] = (y1 - y2) / 2; } ifwtXor(a, h); ifwtXor(a + h, h); } LL n, m; const int C = 1 << 17; LL cnt[C]; int main() { ios_base::sync_with_stdio(0); cin >> n >> m; for(int i = 1; i <= n; ++i) { int x; cin >> x; ++cnt[x]; } fwtXor(cnt, C); for(int i = 0; i < C; ++i) cnt[i] *= cnt[i]; ifwtXor(cnt, C); cnt[0] -= n; for(int i = 0; i < C; ++i) cnt[i] >>= 1; LL ans = 0; for(int i = m + 1; i < C; ++i) ans += cnt[i]; cout << ans << endl; return 0; } 用FWT过了，这题应该是需要字典树做。

import java.util.Arrays; import java.util.Scanner; /** * 第一题AC. */ public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while (in.hasNext()){ int n = in.nextInt(); int[] d = new int[n]; for (int i = 0; i < n; i++) { d[i] = in.nextInt(); } Arrays.sort(d); int l = 1, add = 0; for(int j=1;j<n;j++){ if(d[j]-d[j-1]>20){ if((j-l)%3!=0){ add+=(3-(j-l)%3); l=j; } } } if((n-l+1)%3!=0) add+=(3-(n-l+1)%3); System.out.println(add); } } }

“最少要出几道题” 还可以，异或那题真的难，有人有思路吗

异或那题优化半天，后来默默点了提交！

异或那个也30%

异或那个想了半天都不知道用哪个算法。。

第一道30%搞不动了，第2题简单点AC了

还没来得及看附加题是神魔呢？谁分享一下

最少几道题的，你们的思路呢？ public class JR2 { public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++){ arr[i] = in.nextInt(); } System.out.println(solution(arr)); } public static int solution(int[] arr) { mergeSort(arr, 0, arr.length - 1); int count = 0; int flag = 1; for (int i = 0; i < arr.length - 1; i++) { if (Math.abs(arr[i] - arr[i + 1]) <= 10) { if (flag == 3) { flag = 1; } else { flag += 1; } } else { if (flag == 3) { flag = 1; } else { count += 3 - flag; flag = 1; } } } if (flag!=3){ count+=3-flag; } return count; } public static void merge(int[] arr, int low, int mid, int height) { int i = low; int j = mid + 1; int k = 0; int[] temp = new int[height - low + 1]; while (i <= mid && j <= height) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= height) { temp[k++] = arr[j++]; } for (int m = 0; m < temp.length; m++) { arr[low + m] = temp[m]; } } public static void mergeSort(int[] arr, int low, int height) { if (low < height) { int mid = (low + height) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, height); merge(arr, low, mid, height);   } }

贴一下第一题把，第二题没优化，一直30% #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() {     int n;     while(cin>>n)     {         vector<int> v;         int tmp,sum=0,t1,t2,t3,i;         for(int i=0;i!=n;++i)         {             cin>>tmp;             v.push_back(tmp);         }         sort(v.begin(),v.end());         for(i=0;i<n;)         {             if(i+2<n)             {                 t1=v[i];                 t2=v[i+1];                 t3=v[i+2];                 if(t2-t1>10)                 {                     sum+=2;                     i=i+1;                 }                 else if(t3-t2>10)                 {                     sum+=1;                     i=i+2;                 }                 else                     i=i+3;             }             else                 break;         }         if(i<=n-1)         {             if(i==n-1)                 sum+=2;             if(i==n-2)             {                 if(v[i-1]-v[i-2]<=20)                     sum+=1;                 else                     sum+=4;             }         }         cout<<sum<<endl;     }     return 0; }

第一题 #include<bits/stdc++.h> using namespace std; int main() {       int n;       while(cin>>n)       {             vector<int>d(n);             for(int i=0;i<n;i++)                   cin>>d[i];             sort(d.begin(),d.end());             int count=0;             for(int i=0;i<n-1;i++)             {                   if((d[i+1]-d[i])>10)                         count++;             }             if((n+count)%3==0)                   cout<<count<<endl;             else                   cout<<3-(n+count)%3+count<<endl;       }       return 0; }

一道运行超时间，一道内存溢出。。唉

头条第一题 第二题，trie树没搞出来 #include<iostream> #include<vector> #include<algorithm> using namespace std; int fun(vector<int> x){ sort(x.begin(),x.end()); int i; int sum = 0; int m = 0; for (i = 0; i < x.size()-1;i++){ if (x[i + 1] - x[i]>10){ x.insert(x.begin()+i+1,x[i]+10); sum++; if ((i + 1) % 3 == 0) i++; } } if (x.size() % 3 == 0) return sum; if (x.size() % 3 == 1) return sum + 2; if (x.size() % 3 == 2) return sum + 1; } int main(){ int n; while (cin>>n){ int i; vector<int> x; for (i = 0; i < n;i++){ int tmp; cin >> tmp; x.push_back(tmp); } cout << fun(x)<<endl; } return 0; }

楼上的都是AC  100%的代码么？

最少几道题的那个 不能存在一块排序吧，会超内存啊。

亦或，m的最高1位分割数组，高于i为A，等于i为B，小于i为C，A*（B+C）+AA异或+BC异或为最终值，BC异或可以递归适用上诉办法，AA异或取决于高位1的个数相乘+高位1完全匹配的部分调用BC异或的方法。

/* 第一题 100%AC (异或优化半天还是30%) */ #include <stdio.h> #include <iostream> #include <vector> #include <string> #include <unordered_map> #include <algorithm> using namespace std ; int main() {     int n;     vector < int > nums;     // 注意 while 处理多个 case     while ( cin >> n) {         nums. clear ();         for ( int i = 0 ; i < n; ++i) {             int element;             cin >> element;             nums. push_back (element);         }         sort (nums. begin (), nums. end ());         int sum = 0 ;         int count = 1 ;         int flag = true ;         for ( int i = 1 ; i < n; ) {             int temp = nums[ i ] - nums[ i - 1 ];             if (temp <= 10 ) {                 ++i;                 ++count;                 flag = true ;                 if (count == 3 ) {                     if (i >= n) {                         flag = false ;                         break ;                     }                     ++i;                     count = 1 ;                     flag = true ;                 }             } else if (temp > 10 && temp <= 20 ) {                 if (count == 1 ) {                     i += 2 ;                     ++sum;                     flag = false ;                 } else if (count == 2 ) {                     ++i;                     count = 1 ;                     ++sum;                     flag = true ;                 }             } else if (temp > 20 ) {                 if (count == 1 ) {                     ++i;                     sum += 2 ;                 } else if (count == 2 ) {                     ++i;                     count = 1 ;                     ++sum;                 }                 flag = true ;             }         }         if (count == 1 && flag) {             sum += 2 ;         }         if (count == 2 ) ++sum;         cout << sum << endl ;     }        return 0 ; }