多校第五场归并排序+暴力矩阵乘+模拟+java大数&记忆化递归-白红宇

多校第五场归并排序+暴力矩阵乘+模拟+java大数&记忆化递归

阅读量：6122 次

发布时间：2019-06-21

本文共 4556 字，大约阅读时间需要 15 分钟。

HDU 4911 Inversion

考点：归并排序

思路：这题呀比赛的时候忘了知道能够用归并排序算出逆序数，可是忘了归并排序的实质了。然后不会做……

由于看到题上说是相邻的两个数才干交换的时候。感觉归并排序好像不是得要相邻的呀。然后就这样晕……刚才又一次看了才发现，归并就是相邻的交换的，正好是用来求逆序数的，唉……真的是做这个归并排序比赛就来了……真好！

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define mem(a,b) memset(a,b,sizeof(a))#define lson i<<1,l,mid#define rson i<<1|1,mid+1,r#define INF 510010#define maxn 100010using namespace std;typedef long long ll;typedef unsigned long long ull;ll sum;void merge(ll A[], int p, int q, int r){ int n1 = q - p + 1; int n2 = r - q; ll *L=new ll[n1 + 1]; ll *R=new ll[n2 + 1]; for(int i = 0; i < n1; i++) L[i] = A[p + i]; for(int i = 0; i < n2; i++) R[i] = A[q + 1 + i]; L[n1] = numeric_limits
               
                ::max(); R[n2] = numeric_limits
                
                 ::max(); int i = 0, j = 0; for(int k = p; k <= r; k++) { if(L[i] <= R[j]) A[k] = L[i],i++; else A[k] = R[j],j++,sum += n1 - i; } delete []L; delete []R;}void mergesort(ll A[], int l, int r){ if(l >= r) return ; int q = (l + r) / 2; mergesort(A, l, q); mergesort(A, q + 1, r); merge(A, l, q, r);}ll a[100005];int main(){ //freopen("test.txt","r",stdin); int n,k,i; while(~scanf("%d%d",&n,&k)) { sum=0; for(i=0; i
                 
                  k) printf("%I64d\n",sum-k); else puts("0"); } return 0;}

HDU 4920 矩阵暴力

这题绝对坑死人了，尼玛比赛的时候一直在想那个800矩阵的数据怎么过，假设数据都是1与2，模2根本就不会有0，所以不知道能用什么算法比較快，靠就这样被坑了。

看见这么多人过。还以为别人这么吊呢。靠！然后用了那个什么什么算法忘了，都是T。然后两个小时想不出来怎么搞就放弃治疗了。要是那时知道是这样搞的。尼玛，真想跳楼了比赛的时候！。！！！

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define mem(a,b) memset(a,b,sizeof(a))#define lson i<<1,l,mid#define rson i<<1|1,mid+1,r#define INF 510010#define maxn 100010using namespace std;typedef long long ll;typedef unsigned long long ull;int a[801][801],b[801][801],c[801][801];int main(){ //freopen("test.txt","r",stdin); int n,i,j,k; while(~scanf("%d",&n)) { for(i=0; i

HDU 4915 模拟

这样的题有点像CF上的第二题

不机智就不会了。比赛的时候没想出好的法子来唉……

刚才又看了好久才理解。

假设没有‘?’，问题就变成了简单的括号匹配。这个非常好推断；

每次遇到一个‘?’，我们能够先把这个‘?’变成‘（’，推断是否匹配。再把‘?’变成')',推断是否匹配。

假设都匹配，则有多种匹配方法；

假设都不匹配，则无法匹配；

假设仅仅有一个匹配，则把这个‘?’变成使之匹配的括号，然后继续推断下一个‘?'就可以。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #define mem(a,b) memset(a,b,sizeof(a))#define lson i<<1,l,mid#define rson i<<1|1,mid+1,r#define INF 510010#define maxn 1000010using namespace std;typedef long long ll;typedef unsigned long long ull;char str[maxn],s[maxn];int len;int judge(){ int l=0,r=0,num=0,i;//记录左、右括号和遍历过的字符数 for(i=0;i
              
               num/2) return 0; if(r*2==num) l=r=num=0; } if(l>num/2) return 0; for(i=len-1,l=r=num=0;i>=0;i--) { if(++num==1&&s[i]=='?

') s[i]=')'; if(s[i]=='(') l++; else if(s[i]==')') r++; if(l>num/2) return 0; if(l*2==num) l=r=num=0; } if(r>num/2) return 0; return 1; } int main() { //freopen("test.txt","r",stdin); while(~scanf("%s",str)) { int flag_l,flag_r,i; len=strlen(str); if(len&1) {puts("None");continue;} strcpy(s,str); flag_l=judge();//设没有'?' if(!flag_l) {puts("None");continue;} for(i=0;i<len;i++) { if(str[i]=='?

') { strcpy(s,str); s[i]=')'; flag_l=judge(); s[i]='('; flag_r=judge(); if(flag_l&&flag_r) {puts("Many");break;}; if(!flag_l&&!flag_r) {puts("None");break;} if(flag_l&&!flag_r) s[i]=')'; if(!flag_l&&flag_r) s[i]='('; } } if(i==len) puts("Unique"); } return 0; }

HDU 4919 JAVA大数+记忆化递归

import java.util.*;import java.math.*;import java.io.*;public class Main {	private static BigInteger one=BigInteger.ONE;	private static BigInteger two=BigInteger.valueOf(2);	private static BigInteger three=BigInteger.valueOf(3);	private static BigInteger four=BigInteger.valueOf(4);	private static BigInteger six=BigInteger.valueOf(6);	private static HashMap
     
       map=new HashMap
      
       ();	public static BigInteger dfs(BigInteger n)	{		if(n.equals(two)) return  BigInteger.ZERO;		if(n.equals(three)) return six;		if(n.equals(four)) return  four;		if(map.containsKey(n)) return  map.get(n);		BigInteger ans,k=n.divide(two);		if(n.mod(two).equals(one))			ans=four.multiply(dfs(k)).add(six.multiply(k));		else ans=two.multiply(dfs(k)).add(two.multiply(dfs(k.subtract(one)))).add(four.multiply(k)).subtract(four);		map.put(n,ans);		return  ans;	}	public static void main(String args[])	{		Scanner cin = new Scanner(System.in);		while(cin.hasNextBigInteger())		{			BigInteger n=cin.nextBigInteger();			System.out.println(dfs(n));		}	}}

转载地址：http://dxgka.baihongyu.com/

你可能感兴趣的文章