2014 Multi-University Training Contest 5 出題人————叉姐 隊(duì)內(nèi)訓(xùn)練，感覺有點(diǎn)迷 1001 hdu 4911 Inversion 給一串?dāng)?shù)字，允許交換相鄰的數(shù)字最多k次 找到最少的逆序數(shù) ： (i,j) 有iaj
由組合數(shù)學(xué)知識(shí)，一個(gè)數(shù)組的逆序數(shù)等于使其變成有序列（非降序）所進(jìn)行得相鄰元素交換的最少次數(shù)。 仔細(xì)想想，i,j,k swap(i,j) 并不會(huì)影響k的逆序數(shù)
所以這題就是 逆序數(shù)-k; 用線段樹就好了 之前2016 多校補(bǔ)題補(bǔ)過逆序數(shù)，但那個(gè)題是1-n的全排列，所以沒有相同的ai，這里需要離散化。這里“ 按位置插線段樹“ 也很精髓
#include<iostream>#include<cstdio>#include<algorithm>#include<vector>#include<queue>#include<stack>#include<string.h>#include<map>#include<set>using namespace std;#define ll __int64/* */struct seg{ int l,r; ll v;}st[100005<<2];void build(int l,int r,int id){ int mid=(l+r)>>1; st[id].v=0; st[id].l=l; st[id].r=r; if(l==r) return; build(l,mid,id<<1); build(mid+1,r,(id<<1)+1);}void push_up(int id){ st[id].v=max(st[id].v,st[id<<1].v+st[id*2+1].v);}void update(int p,int id){// 1009 Exclusive or 題意 不知， 小學(xué)弟直接把公式交給我，我打大數(shù)模板就好了，穩(wěn)。 這里找了一個(gè)比較好的大數(shù)模板，因?yàn)樾枰褂糜洃浕阉鳎€需要學(xué)一下map該如何使用。 import java.util.*;import java.math.*; import java.io.*;import java.util.Scanner; public class Main { public static BigInteger bigInteger0=BigInteger.valueOf(0); public static BigInteger bigInteger1=BigInteger.valueOf(1); public static BigInteger bigInteger2=BigInteger.valueOf(2); public static BigInteger bigInteger4=BigInteger.valueOf(4); public static BigInteger bigInteger6=BigInteger.valueOf(6); public static HashMap<BigInteger,BigInteger> map=new HashMap<BigInteger,BigInteger>(); public static BigInteger dfs(BigInteger n){ if(map.containsKey(n)) return map.get(n); BigInteger ans=BigInteger.valueOf(0); BigInteger t=n.divide(bigInteger2); BigInteger r=n.remainder(bigInteger2); BigInteger a=new BigInteger ("1"); BigInteger b=new BigInteger ("1"); a=dfs(t); b=dfs(t.subtract(bigInteger1)); if(r.equals(bigInteger1)) ans=( bigInteger4.multiply(a) ).add(bigInteger6.multiply(t)); else { ans=bigInteger2.multiply(a); ans=ans.add(bigInteger2.multiply(b)); ans=ans.add(bigInteger4.multiply(t)); ans=ans.subtract(bigInteger4); } map.put(n, ans); return ans; } public static void main(String[] args) { Scanner cin = new Scanner (System.in); BigInteger x; map.put(bigInteger0, bigInteger0); map.put(bigInteger1,bigInteger0); while(cin.hasNext()) { x=cin.nextBigInteger(); System.out.println(dfs(x)); } }}1010 Matrix multiplication 題意很簡(jiǎn)單：求兩個(gè)矩陣相乘 800*800的矩陣
最讓我沒想到的是： 判斷會(huì)比相乘的時(shí)間還要多。 以后做常數(shù)優(yōu)化，記住： 稍作判斷，寧愿做運(yùn)算，也盡量少做判斷。還有貌似a=a+b，比a+=b, 要快，（沒驗(yàn)證過，不知真假）
#include<iostream>#include<cstdio>#include<algorithm>#include<vector>#include<queue>#include<stack>#include<string.h>#include<map>#include<set>using namespace std;#define ll __int64/*把 每i行的第j個(gè) 放進(jìn) map<pair<i,j>,int >所以 aij *bji 存在int */int matr1[805][805];int matr2[805][805];int matr3[805][805];int main() { //freopen("1.txt","r",stdin); int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&matr1[i][j]),matr1[i][j]%=3; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&matr2[i][j]),matr2[i][j]%=3; memset(matr3,0,sizeof(matr3)); for (int i=1;i<=n;i++){ for (int k=1;k<=n;k++){ if(matr1[i][k]) for (int j=1;j<=n;j++){ matr3[i][j]+=matr1[i][k]*matr2[k][j]; } } } for (int i=1;i<=n;i++){ printf("%d",matr3[i][1]%3); for (int j=2;j<=n;j++){ printf(" %d",matr3[i][j]%3); } printf("/n"); } } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
