2012年8月4日星期六

[20120805]關於mediainfo.dll,JNative.jar和一圖流視頻

最近由於某個魔炮廚(注:不是zbwmqlw)拜託我做一組一圖流視頻,然後我看到一共57首mp3然後我就傻了,於是就想做個批量的工具批量處理掉.
[地球人]都知道,ffmpeg可以用來生成一圖流視頻,但是,一個很禿的一點是,ffmpeg生成視頻需要手動輸入視頻時間.然後如果單純的用bat執行的話沒法獲得音頻的時間,所以我就傻了.
無奈於是只好考慮寫一個程序解決掉.[地球人]都知道.java裏面可以用Rumtime.getRuntime.exec("cmd /c "+command)來執行cmd命令,所以問題的關鍵就是,如何獲取要處理的音頻的長度.
一開始,我準備用javax.sound.sample.AudioFileFormat來獲取音頻的時間長度,結果後來很快發現,AudioFileFormat竟然連mp3格式都不支持,於是我就傻了
要 處理mp3格式還需要額外安置解碼器,出於節省cpu消耗的考慮我最後果斷放棄了AudioFileFormat,轉而考慮mediainfo.一開始我 考慮的是運行mediainfo.exe,獲取其stderr,并進行字符串處理獲取時間長度.不過很禿的是我懶得寫字符串處理,於是我最後決定使用 mediainfo.dll,藉助mediainfo直接獲取音頻長度.
[地球人]都知道,java要使用dll需要JNI,或者 JNative.爲了方便,於是我選用的JNative.mediainfo在其dll的下載包中附帶了一個 MediaInfoDLL.JNative.java,作為java調用mediainfo的API.有了這個,程序就好寫多了.獲取音頻長度之後運行 ffmpeg,程序的主體就完成了.
最後再加點細節,程序最後就完工了

package JMake;
import java.io.*;
import java.util.*;
import java.util.regex.*;
import javax.sound.sampled.*;
import org.xvolks.jnative.*;
import org.xvolks.jnative.exceptions.*;
import org.xvolks.jnative.pointers.*;
import JMake.*;
public class JMake{
  static MediaInfo mediainfo;
  static int find(String args[],String s){
    if(args==null)
      return -1;
    if(s==null)
      return -1;
    for(int i=0;i<args.length;i++)
      if(s.compareTo(args[i])==0)
        return i;
    return -1;
  }
  static ArrayList getPatternFiles(File file,Pattern p,boolean subDir){
    if(file==null)
      return null;
    if(file.isFile()){
      Matcher fMatcher=p.matcher(file.getName());
      if(fMatcher.matches()){
        ArrayList list=new ArrayList();
        list.add(file);
        return list;
      }
    }
    if(file.isDirectory()){
      File[] files=file.listFiles();
      if((files!=null)&&(files.length>0)){
        ArrayList list=new ArrayList();
        for(int i=0;i<files.length;i++){
          if(files[i].isDirectory()&&(!subDir))
            continue;
          ArrayList tmp=getPatternFiles(files[i],p,subDir);
          if(tmp!=null)
            list.addAll(tmp);
        }
        return list;
      }
    }
    return null;
  }
  static File[] getFiles(String dir,String s,boolean subDir){
    File file=new File(dir);
    s=s.replace('.','#');
    s=s.replaceAll("#", "\\\\.");
    s=s.replace('*','#');
    s=s.replaceAll("#",".*");
    s=s.replace('?','#');
    s=s.replaceAll("#",".?");
    s="^"+s+"$";
    Pattern p=Pattern.compile(s);
    ArrayList files=getPatternFiles(file,p,subDir);
    File[] ret=new File[files.size()];
    files.toArray(ret);
    return ret;
  }
  static void runCommand(Runtime run,String s)throws Exception{
    Process process=run.exec("cmd /c "+s);
    Scanner in=new Scanner(process.getErrorStream());
    for(;in.hasNext();System.out.println(in.nextLine()));
    in.close();
    process.waitFor();
    return;
  }
  static void generateFLV(String pic,String audio)throws Exception{
    long len=0;
    mediainfo.Open(audio);
    mediainfo.Option("Complete","0");
    String len1=mediainfo.Get(MediaInfo.Stream_General,0,"Duration",MediaInfo.Info_Text,MediaInfo.Info_Name);
    len=(long)(Math.floor((Long.parseLong(len1)/1000)))+1;
    StringBuffer command1=new StringBuffer("ffmpeg ");
    command1.append("-loop_input -r 1 -t "+Long.toString(len)+" ");
    command1.append("-i \""+pic+"\" ");
    command1.append("-vcodec libx264 ");
    command1.append("-crf 24 -coder 1 -flags +loop -cmp +chroma ");
    command1.append("-partitions +parti8x8+parti4x4+partp8x8+partb8x8 -me_method umh -subq 7 -me_range 16 ");
    command1.append("-g 250 -keyint_min 1 -sc_threshold 40 -b_strategy 2 -bf 0 -refs 6 ");
    command1.append("-qcomp 0.6 -qdiff 4 ");
    command1.append("-directpred 3 -trellis 2 -flags2 +wpred+mixed_refs+dct8x8+fastpskip ");
    command1.append("-y -f mp4 \""+audio+".mp4\"");
    StringBuffer command2=new StringBuffer("ffmpeg ");
    command2.append("-vcodec copy -i \""+audio+".mp4\" ");
    command2.append("-acodec copy -i \""+audio+"\" ");
    command2.append("-y -f flv \""+audio+".flv\"");
    System.out.println(command1);
    System.out.println(command2);
    Runtime run=Runtime.getRuntime();
    runCommand(run,command1.toString());
    runCommand(run,command2.toString());
    return;
  }
  public static void main(String args[])throws Exception{
    int picPattern=find(args,"--pic")+1;
    if(picPattern==0)
      return;
    int audioPattern=find(args,"--audio")+1;
    if(audioPattern==0)
      return;
    boolean subPicDir=(find(args,"--sub-pic-dir")+1!=0);
    boolean subAudioDir=(find(args,"--sub-audio-dir")+1!=0);
    File tmpPic=new File(args[picPattern]);
    File[] pics=getFiles(tmpPic.getParent(),tmpPic.getName(),subPicDir);
    File tmpAudio=new File(args[audioPattern]);
    File[] audios=getFiles(tmpAudio.getParent(),tmpAudio.getName(),subAudioDir);
    String dllPath="MediaInfo.dll";
    mediainfo=new MediaInfo(dllPath);
    for(int i=0;i<Math.min(pics.length,audios.length);i++)
      generateFLV(pics[i].getPath(),audios[i].getPath());
    if(pics.length<audios.length)
      for(int i=pics.length;i<audios.length;i++)
        generateFLV(pics[pics.length-1].getPath(),audios[i].getPath());
    if(pics.length>audios.length)
      for(int i=audios.length;i<pics.length;i++)
        generateFLV(pics[i].getPath(),audios[audios.length-1].getPath());
    return;
  }
}

2011年10月21日星期五

PrintWriter.print()和PrintWriter.printf()效率對比

測試平臺:
硬件:IBM ThinkPad X60,Intel T2400 CPU+1G DDR2
軟件:JDK1.6
測試用程序:
測試PrintWriter.print()用程序:
import java.io.*;
import java.text.*;
public class PrintTest{
  public static void main(String args[])throws IOException{
    PrintWriter output=new PrintWriter(new FileWriter("out.txt"));
    long time1=System.currentTimeMillis();
    DecimalFormat fmt=new DecimalFormat("0.######");
    for(int i=0;i<10000000;i++)
      output.println(fmt.format(i));
    long time2=System.currentTimeMillis();
    output.close();
    output=new PrintWriter(System.out);
    output.println(Long.toString(time2-time1)+" ms.");
    output.close();
  }
}
測試PrintWriter.printf()用程序:
import java.io.*;
public class PrintfTest{
  public static void main(String args[])throws IOException{
    PrintWriter output=new PrintWriter(new FileWriter("out.txt"));
    long time1=System.currentTimeMillis();
    double d=4.6;
    for(int i=0;i<10000000;i++)
      output.printf("%.6f\n",d);
    long time2=System.currentTimeMillis();
    output.close();
    output=new PrintWriter(System.out);
    output.println(Long.toString(time2-time1)+" ms.");
    output.close();
  }
}
測試結果:
給咱的破本子給跪了Orz...循環才一千萬就一個個跑這麼長時間Orz...
另外在一開始的時候printf()曾經拋出過這樣一個異常來:
Exception in thread "main" java.util.UnknownFormatConversionException: Conversion = 'l'
    at java.util.Formatter$FormatSpecifier.conversion(Unknown Source)
    at java.util.Formatter$FormatSpecifier.<init>(Unknown Source)
    at java.util.Formatter.parse(Unknown Source)
    at java.util.Formatter.format(Unknown Source)
    at java.io.PrintWriter.format(Unknown Source)
    at java.io.PrintWriter.printf(Unknown Source)
    at PrintfTest.main(PrintfTest.java:8)
由於JDK1.5的時候SUM還沒有被甲骨文收購,所以我只想說:"DOG SUN的SUN我SUN[你妹的敏感词]"
直接用Formatter來實現print(),這不是逼人用print()么……

2011年10月7日星期五

[轉載]所以說蟲族的MMM組合在後期對付人族實在是太好用了混蛋!

下面插播一條新聞:

10月新番Fate/Hollow Ataraxia第一话《我的赛巴不可能那么伊利亚》在 BILIFUN动画上以全国方言播出,引起广大死宅激烈反响。众多塞巴控表示KEY的动画第一次这么血腥,大量资深月厨无地自容表示以后再也不玩KID的 游戏了;但也有少数猎奇爱好者觉得虽然没看过原作,不过只要有くすくす的剧本、梶浦由纪的人设再加上七尾奈留监督就一定要看,毕竟上次这样的阵容还是在 《魔法少女立华奏》那时的事了。
以下为各位死宅的评论:
>>FHA真是宇宙第一神作啊,虚渊玄唱的OP“幽雅に咲かせ、墨染 の桜”碉堡了!新番里也只有同在Liar的武内茸唱得比他好了,不过要说到编曲还是N+的钢屋更成熟一些。至于声优的话,川澄綾子的声优るーすぼーい作为 新人刚出道就能达到如此程度,实在令人赞叹,可惜B叔的声优换成了片冈とも卖萌的时候再也听不到べっかんこう那经典的棒读了。
>>哎~!不给力啊,画面崩的像秽翼里的卷心菜似的,这也算是业界最高水平的《この失われた星空に約束を》的动画吗?还好有穹妹在里面卖萌,不然的话我真是看不下去了。要说这么崩的画,也就今年萌战里的花鸡了,虽然还是西柚大妈画的。
>>这H场景简直就像一路神的CG动画一样流畅,不愧是诚哥(新海诚)啊,如果大枪看到如此的演出水平,不知道A社还会不会关门了。嘛,不过关了也好,现在也只有AB2还敢出无H无语音无选项的游戏,还附带个无发售日。
>> 葵未来最高!什么丸户史明和她比起来战斗力只有5,话说回来,优子姐姐也不错啊,金发双马尾+战斗服绝对领域真是无口角色中的何小洋。再往下说的话也只有 夏海里伽子能和优子姐姐相提并论了,里伽子在LeMU打工的时候第一次遇到了孔涛罗,命运的邂逅引发了世界的危机,所以时田雪和海斗才会来到地球。
>> 喂楼上你不要剧透啊!可恶你剧透我也想要剧透了……所以之后坂上智代由于种种原因坐上了メガラフター,与邪恶的聖書之獣水坂怜在漆黒のネオスフィア展开决 战!为了获得圣杯,法月将臣使用了禁断的秘技九鬼流奥义《アイギス》导致了网络世界的崩溃。最后的超展开我就不说了!不愧是健速写的剧本啊,比起AGE的 麻枝和LEAF的打越真是震撼多了。
>>你们连剧透要反白都不懂吗?虽然在CK只能反黄(?)大泉君最终找到了掌握着整个世界命运的 早坂日和,却得知想要推倒水素,必须先打通抹布拉布!不得已,朝仓音梦只能来到ゆのはな町,穿上了传说中的圣衣カルタグラの殻,试图回到过去,使大十字九 郎觉醒,从而互相结束生命结束这漫长的旅程,但万万未曾想到的是,九郎已经另结新欢,将草壁辽一收入后宫,并习得了劫之眼。最后在不断LOOP之中,仓成 武觉醒成为了妹控,与向坂环结为兄弟,在鶴見駅过起了隐姓埋名的卖豆腐送货生活。如此波澜壮阔的超展开,你们在看动画之前该先去玩原作吧!不要怪我嘲讽你 们,和原作比这动画版就是渣渣啊!
>>GIGA的游戏里我现在最期待的还要算是星空めてお的新作《いろとりどりのWORKS》,自从 剧场版化取消转为漫画版之后,我已经等了2年了,希望这次的演出能超过《明日の蔵女と逢うために》的水平啊!这次GIGA把原田雄一也拐过来了,他是我最 喜欢的作曲家之一,配上星空的文字和しろ的HCG那真是没话说了,业界黄金组合。这么说来N+上次一下公布3新作,《祝福のプロミア子》也挺让人在意的, 毕竟有田中罗密欧+司田トモセ+中央タカヒロ的剧本和杉菜水姬+王雀孫+CARNELIAN的原画啊。

2011年9月25日星期日

2011 ACM-ICPC Dalian Regional

9.24-9.25是大連地區賽,之前似乎是因為我們sdu在之前的網絡賽中表現不錯,結果我們竟然獲得了兩個正式隊名額,於是峰哥非常囧的找我和 dxh詢問二隊組隊方案.最後在"有名額浪費掉那純屬半禿"的原則指導下,找到張夢馳神牛隨便湊了個隊,準備去大連打醬油.於是我和dxh兩個大一的就能 夠在開學還沒多久之後就可以參加Regional了……這樣山大就兩個正式隊,一個旅遊隊,雖然我覺得我們隊更像是旅遊的……
去acm官網註冊的時候,我們因為我們的隊名起了爭執.dxh認為"WrongAnser"這個名字不錯,結果當場被峰哥卷了.最後我表示"SuperBrother"這個當隊名就不錯,不過結果是我被峰哥和dxh鄙了,半禿度+1.
去 大連買的是9.23下午4點的灰機.我坐飛機的第一次就這樣獻給了海南航空公司.之後去大連理工,報到,辦手續.順便說一下貌似很多人都喜歡把大連理工叫 做"大工",不解釋……住處"略"坑爹,坑爹到我只好蹭dxh的無線網卡上網.面對著我用掉的20+M流量我表示壓力很大……
因為是純屬打 醬油的二隊,所以晚上玩的很嗨,一直到半夜.第二天下午有熱身賽,我們第一次接觸到了比賽場地.機器用的吾半禿10.10,配備 code::blocks,Eclipse和Netbeans.機子的運算速度很快,實際測試了一下發現一億次整數運算0.2s就跑完,浮點運算3.Xs 就跑完,然後測了一下,發現跑一億次java.math.BigInteger也是各種無壓力,3.Xs直接完成.然後看到c和c++的編譯指令都有 -o2優化,只能說"I'm SO HAPPY~~".熱身賽比賽中間有人提交Clarification詢問內存限制,回覆是只要不把評測機總內存吃掉就大丈夫,並且聲稱評測機和比賽機配 置一樣.此時已經很明顯了,時間和空間複雜度都不會卡常數和低階項,基本上只要能有合適的想法,能寫對,就能ac.順縣說下我們在c13處,c12就是中 山大學.熱身賽的時候thu某支隊費了力氣ak掉四道題,把sjtu壓了下去,結果很快中山大學也ak了,又把thu的那隻隊伍壓倒第二去了囧……表示坐 在中山大學主力隊伍後面的我們感到亞歷山大.
"熱身賽你們ak個毛啊,這樣很掉rp的知道不"---熱身賽后某神牛的憤怒.
順便說下之前我們一直認為一個隊180大洋的伙食費絕對足夠,結果由於本人這個大吃貨,面對著9.23晚上第一頓飯就吃掉50大洋的情況,我們最後果斷找張洋那個隊來接濟了我們9.25的早飯……以後組acm隊的時候一定要考慮到隊員的飯量問題啊TAT.
9.25 9:00-14:00正式比賽.和熱身賽不同的是氣球的展示位置變了…… 比賽開始后我們速度開始分頭讀題,於是乎我果斷跑去看H,I和J.然後我發現H題是個計算幾何我表示此時只能仰天召喚mj神牛.I題讓你求比n小並且和n 互質的所有數的四次方的和,看到n<=10^8,再看到1000組測試數據,表示果斷蛋疼.J題讀題花的時間最長.一開始照著題目描述發現樣例貌似 說的不對勁,然後我發現白色部份必須是正方形Orz...然後我列了兩個整數方程之後就表示不可做,扔了……事實證明這是我比賽時候一個相當大的失誤.我 應該早點發現這可能和二分圖最小覆蓋有聯繫,並且說出來……我半禿.此時張夢馳發現D是一道大水的模擬,於是dxh果斷上去coding.但是幾個模擬規 則著實噁心到了我們,於是在WA了好幾次后我們才把D題掉ac掉了...
此時張夢馳發現C題可能可做,於是我去看C題了,結果除了猜想從中 間按按鈕一定不會最優就沒別的成果了.然後dxh發現G題果斷是個trie圖,然後我們三個都不會寫……翻閱模板,結果發現模板裏面什麽都有就是沒 trie圖的……然後dxh看C,我掃了一眼F.我一看:我艸?這種題我在vijos上還做過呢,不就是200棵線段樹么,種了!然後我生成自己線段樹比 較穩定,所以我就上去敲F了,可是沒想到,這是我杯具的開始……開橋之後才發現自己好長時間沒敲手生了不知道多少,看到的模板的別人的,自己根本不習慣這 個寫……好在這題不難,死磕了半個小時之後程序基本完工.敲樣例上去測試結果發現自己RTE,用gdb調了一段時間后dxh表示自己要上機敲C,於是我打 印下來代碼自己看.dxh敲完之後調試過了樣例,submit之後返回RTE,於是dxh下機,我上去再去調試F...這樣的循環很快以dxh因為某個很 奇怪的改動而ac掉C結束,於是接下來dxh和張夢馳開始對E,G,I感興趣,我則在苦逼地調試F.基本上比賽下半段的時間全給我用來調試了,可是我的結 果不是RTE就是WA,一直到比賽結束都沒AC...其中有幾次因為過於緊張,犯了很多低級錯誤,結果使我們隊增加了好多罰時……嘛不過最後也沒ac,這 些罰時也無所謂了╮(╯_╰)╭
比賽的最後階段,我們聽到c12的中山大學說了一句I用匈牙利可做,然後沒多久我們就聽到了中山那一隊里ac題的歡呼聲,我們看著中山那一隊升起的8個氣球,表示亞歷山大……
這次比賽峰哥那一隊確實囧了.最後拿了個銅回來,這讓最後一次參加acm的冰哥和遠哥情何以堪......
整場比賽場內場外只有一個人注意到我們隊的奇葩的名字……我表示我囧.
比賽結束后sdu全員在旁邊的一家上校餐廳里呆到晚上,然後坐車去的機場,凌晨回到學校,通宵玩遊戲玩到現在,然後開始寫這些東西,一直寫到現在.

2011年9月21日星期三

北郵的死宅數敢更多一些么= =|||||||||||||

RT.之前北京賽區網絡賽Problem B(http://boj.me/problem/ProblemSet/B.pdf)扯到小圓臉,Problem D(http://boj.me/problem/ProblemSet/D.pdf)扯到FXTZ.這次又在SGU上看到某人(http: //acm.sgu.ru/teaminfo.php?id=015656),昵稱大亮啊!而且這個sgu id看上去應該是很早註冊的了(我09年初註冊的sgu,結果id是020695...)

2011年9月19日星期一

改變我的代碼風格的確是一件非常困難的事情

你哥我淪落到開vpn來上blogger了,杯具啊!
最近做狀壓動規做上癮了.hdu3920.一看就知道這不是個禿論.
方程:dp[s|(1<<i)|(1<<j)]=dp[s]+min(cost(i,j));
注意幾點
1.顯然當確定要消去i點和j點的時候,就應該貪心地先消去里起始點最近的點
2.轉移時可以限制i是按照標號順序可以被消去的第一個點,然後直接只枚舉j.這樣狀態不會減少,轉移複雜度大大減少.
3.這狀態轉移方程的拓撲關係比較混亂,所以可以根據這個轉移方程建立一個有向圖然後廣搜一遍.
source code:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;
#define maxn 21
#define clr(a) memset(a,0,sizeof(a))
#define inf (1000000000)
const int maxs=(1<<20);
struct point{
  double x,y;
};
point p[maxn];
point st;
double dp[maxs];
int q[maxs+2];
double tmpd;
int testcase,ff,rr,n,s;
inline double sqr(double a){
  return a*a;
}
inline double dis(point a,point b){
  return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
bool compare(const point &a,const point &b){
  return dis(st,a)<dis(st,b);
}
int main(){
  freopen("in.txt","r",stdin);
  scanf("%d",&testcase);
  for(int ttestcase=1;ttestcase<=testcase;++ttestcase){
    printf("Case #%d: ",ttestcase);
    scanf("%lf%lf",&st.x,&st.y);
    scanf("%d",&n),n+=n;
    for(int i=0;i<n;i++)
      scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p,p+n,compare);
    s=(1<<n);
    for(int i=1;i<s;i++)
      dp[i]=inf;
    dp[0]=0,ff=1,rr=0,q[1]=0;
    for(int tmp,i,j,tmps;rr<ff;){
      tmp=q[++rr];
      for(i=0;i<n;i++)
        if(!(tmp&(1<<i)))
          break;
      for(j=i+1;j<n;j++)
        if(!(tmp&(1<<j))){
          tmps=(tmp|(1<<i)|(1<<j));
          tmpd=dp[tmp]+dis(st,p[i])+dis(p[i],p[j]);
          if(dp[tmps]>tmpd){
            if(dp[tmps]>=inf)
              q[++ff]=tmps;
            dp[tmps]=tmpd;
          }
        }
    }
    printf("%.2lf\n",dp[s-1]);
  }
  fclose(stdin);
  return 0;
}

2011年9月15日星期四

过去的「訓読み」碉堡了

http://www001.upp.so-net.ne.jp/dassai/suishi/suishi_yomi.htm
出師表 三國志 蜀書 卷五 諸葛亮伝

(臣亮言う)先帝創業未(いま)だ半ばならざるに中道に崩(ほうそ)したまう。今、天下三分して益州疲弊せり。これ誠に危急存亡の秋(とき)なり。

然れども侍衛の臣内に懈
(おこた)らず、忠志の士身を外に忘るる者は蓋(けだ)し先帝の殊遇を追いて之を陛下に報ぜんと欲するなり。誠に宜しく聖聴を開張し、以て先帝の遣德を光(かがや)かし、志士の気を恢弘(かいこう)すべし。宣しく妄りに自ら菲薄(ひはく)し、喩(たとえ)を引いて義を失い、以て忠諌の路を塞ぐべからざるなり。

宮中・府中倶
(とも)に一体爲(た)り。臧否(ぞうひ)を陟罰(ちょくばつ)するに宜(よろ)しく異同あるべからず。若(も)し奸(かん)を作(な)し、科(とが)を犯し、及び忠善を爲す者有らば、宣しく有司に付して其の刑賞を論じ、以て陛下平明の理を昭(あきらか)にすべし。宜しく偏私(へんし)して内外をして法を異(こと)にせしむべからざるなり。

侍中・侍郎の郭攸之
(かくゆうし)・費(ひい)・董允(とういん)等は、これ皆な良実、志慮忠純なり。是(ここ)を以ちて先帝簡抜して以て陛下に遣(のこ)せり。愚、以爲(おもえらく)、宮中の事は事大小と無く悉(ことごと)く以て之に咨(はか)り、然る後に施行せば必ず能く闕漏(けつろう)を稗補(ひほ)し広く益する所有るなり。将軍の向寵(しょうちょう)は性行淑均(しゅくきん)にして軍事に暁暢(ぎょうちょう)す。昔日に試用せられ先帝之を称して能(のう)と曰(い)えり。是(ここ)を以ちて衆議して寵を挙げて督(とく)と爲す。愚、以爲(おもえら)く、営中の事は悉く以って之に咨(はか)れば必ず能く行陣をして和睦し優劣をして所を得しめんと。

賢臣に親しみ小人を遠ざけしは此れ先漢の興隆せし所以
(ゆえん)なり。小人に親しみ賢臣を遠ざけしは此れ後漢の傾頽(けいたい)せし所以なり。先帝在(あ)りし時、臣と此の事を論ずる毎(たび)に未だ嘗(かつ)て桓霊に歎息痛恨せずんばあらざりき。侍中・尚書・長史・参軍、此れ悉く貞亮(ていりょう)にして節に死するの臣なり。願わくば陛下之に親しみ之を信ぜよ。則ち漢室の隆(さかん)なること日を計りて待つべきなり。

臣、本
(もと)布衣(ふい)にして躬(みずか)ら南陽に耕し、荀(いやしく)も性命を乱世に全うせんとして聞達(ぶんたつ)を諸侯に求めず。先帝、臣の卑鄙(ひい)なるを以てせず、猥(みだり)に自ら枉屈(おうくつ)して三たび臣を草廬の中に顧み、臣に諮(はか)るに当世の事を以てす。是(これ)に由(よ)りて感激し遂に先帝に許すに駆馳(くち)を以てす。後、傾覆(けいふく)に値(あ)い、任を敗軍の際に受け、命を危難の間に奉ず。爾来二十有一年。先帝、臣の謹慎なるを知る。故に崩ずるに臨み臣に寄するに大事を以てしたまえり。命を受けて以来、夙夜(しゅくや)憂歎(ゆうたん)し託付の效あらずして以て先帝の明を傷(そこな)うことを恐る。故に五月、瀘(ろ)を渡り深く不毛に入れり。今、南方已に定まり甲兵已に足る。当に三軍を奨率し北のかた中原を定むべし。庶(こいねが)わくば駑鈍(どどん)を竭(つく)し奸凶を壤除(じょうじょ)し漢室を興復し旧都に還さんことを。此れ臣が先帝に報い而して陛下に忠なる所以の職分なり。損益を斟酌し忠言を進め尽すに至りては、則ち攸之(ゆうし)・(い)・允(いん)の任なり。願わくば陛下、臣に託するに討賊・興復の效を以てせよ。效あらずんば則ち臣の罪を治め以て先帝の霊に告げ、若し興德の言無くんば則ち攸之(ゆうし)・(い)・允(いん)等の慢を責め、以て其の咎(とが)を彰(あらわ)せ。陛下も亦た宣しく自ら謀り、以て善道を諮諏(ししゅ)し、雅言を察納し深く先帝の遣詔を追うべし。

臣、恩を受くるの感激に勝
(た)えず。今、遠く離るるに当り表に臨みて涕(なみだ)(お)ちて言う所を知らず。

2011年9月14日星期三

連MAZE這種題我都做了好久我弱爆了……

HDU4035,11號網絡賽的MAZE,這道遞推因為我把幾個區域變量【優化】到了全局結果一直WA,然後我就禿了……
算法:
這個禿雖然是個無根樹,但是由於樹根是確定的了,所以實質上就是個有根樹.設e[i]是以點i為子樹走出迷宮所需的數學期望,那麼可以【得知】,對於任意一個e[i],其結果一定是一個關於e[1],e[fa[i]]的一次多項式,即我們這裡可以設e[i]=r[i]*e[1]+x[i]*e[fa[i]]+a[i].那麼對於任意一個點i,都有e[i]=k[i]*e[1]+tmp[i]*(e[fa[i]]+sum(e[j],j為i的兒子)+1),其中tmp[i]=(1-k[i]-e[i])/cnt[i],cnt[i]即點i的度..又因為e[fa[j]]=e[i],j是i的兒子,所以,我們可以發現,e[i]中的三個係數r[i],x[i]和a[i]都可以由i的兒子節點們給遞推出來.這樣遞推到最後,這種會發現e[1]=r[1]*e[1]+a[1],此時就相當於解一個關於e[1]的一元一次方程,解出來即可.
source code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define maxn 10010
#define eps (1e-10)
#define clr(a) memset(a,0,sizeof(a))
struct edge{
  int vt,next;
};
edge e[maxn*5];
double K[maxn],E[maxn],r[maxn],x[maxn],a[maxn],tmp[maxn];
int fa[maxn],cnt[maxn],st[maxn];
bool vis[maxn];
int testcase,n,tot,p,q;
double ttmp;
bool flag;
int sig(double x){
  return (x>eps)-(x<-eps);
}
int addedge(int u,int v){
  e[++tot].vt=v,e[tot].next=st[u],st[u]=tot;
  return 0;
}
int dfs1(int u){
  cnt[u]=0;
  for(int i=st[u];i!=0;i=e[i].next){
    ++cnt[u];
    if(!vis[e[i].vt])
       vis[e[i].vt]=true,fa[e[i].vt]=u,dfs1(e[i].vt);
  }
  tmp[u]=(1-K[u]-E[u])/cnt[u];
  return 0;
}
int dfs2(int u){
  if(vis[u])
    return 0;
  vis[u]=true;
  r[u]=x[u]=a[u]=0;
  double R=0,X=0,A=cnt[u];
  for(int i=st[u];i!=0;i=e[i].next){
    if(e[i].vt==fa[u])
      continue;
    dfs2(e[i].vt);
    R+=r[e[i].vt],X+=x[e[i].vt],A+=a[e[i].vt];
  }
  R*=tmp[u],X*=tmp[u],A*=tmp[u];
  if(sig(ttmp=1-X)==0)
    flag=false;
  if(flag)
    r[u]=(K[u]+R)/ttmp,x[u]=tmp[u]/ttmp,a[u]=A/ttmp;
  return 0;
}
int main(){
  scanf("%d",&testcase);
  for(int ttestcase=1;ttestcase<=testcase;++ttestcase){
    printf("Case %d: ",ttestcase);
    clr(st);
    scanf("%d",&n);
    tot=0;
    for(int i=1;i<n;i++){
      scanf("%d%d",&p,&q);
      addedge(p,q),addedge(q,p);
    }
    for(int i=1;i<=n;i++){
      scanf("%lf%lf",K+i,E+i);
      K[i]/=100.0,E[i]/=100.0;
    }
    flag=true;
    clr(vis),vis[1]=true;
    dfs1(1);
    clr(vis),vis[1]=true;
    for(int i=2;i<=n;i++)
      dfs2(i);
    if(!flag){
      printf("impossible\n");
      continue;
    }
    double X=0,A=0;
    for(int i=st[1];i!=0;i=e[i].next)
      X+=x[e[i].vt]+r[e[i].vt],A+=a[e[i].vt]+1;
    X*=tmp[1],A*=tmp[1];
    if(sig(ttmp=1-X)==0){
      printf("impossible\n");
      continue;
    }
    printf("%.6lf\n",A/ttmp);
  }
  return 0;
}

2011年9月9日星期五

我該說是sgu的評測機奇葩還是我本機的評測環境奇葩

本來指望把sgu502當作水題刷一下的,結果事實證明無論你在本機上測試多么沒問題,上sgu必須把數組開的足夠大,否則就等著RTE吧. 
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define maxn 19
#define maxs (1<<18)
int dp[maxs][19];
int dt[maxn];
char str[255];
int n,s;
bool search(int a,int b){
  if(a==0)
    return b==0;
  if(dp[a][b]==0)
    return false;
  if(dp[a][b]==1)
    return true;
  for(int ta,tb,i=1;i<=n;i++){
    if((a&(1<<(i-1)))==0)
      continue;
    ta=a^(1<<(i-1)),tb=(b-dt[i]+17)*12%17;
    if((ta==0)&&(dt[i]==0))
      continue;
    if(search(ta,tb))
      return dp[a][b]=1,true;
  }
  return dp[a][b]=0,false;
}
int print(int a,int b){
  if(a==0)
    return 0;
  for(int ta,tb,i=1;i<=n;i++)
    if((a&(1<<(i-1)))!=0){
      ta=a^(1<<(i-1)),tb=(b-dt[i]+17)*12%17;
      if((ta==0)&&(dt[i]==0))
        continue;
      if(search(ta,tb))
        return print(ta,tb),printf("%d",dt[i]),0;
    }
  return 0;
}
int main(){
  scanf("%s",str);
  n=strlen(str);
  if(n==18){
    printf("-1\n");
    return 0;
  }
  for(int i=1;i<=n;i++)
    dt[i]=str[i-1]-'0';
  s=(1<<n)-1;
  for(int i=0;i<=s;i++)
    for(int j=0;j<17;j++)
      dp[i][j]=-1;
  if(search(s,0))
    print(s,0);
  else
    printf("-1");
  printf("\n");
  return 0;
}

2011年8月26日星期五

原來♂兄貴引導人民♂的典故源遠流長啊

今天去nico看了看本家,頓時感到一股迷之♂感動
-----------------
■世界的ガチムチバンド・ COLTPLAYの新曲は、遙か昔、帝政末期の新日暮里で市民革命を成し遂げた伝説の英雄達に捧げられた生命賛歌である。 ■賢帝、キング石井亡き後の動 乱で権力を握り、暴虐の限りを尽くした宰相TDNコスギ。 その彼のパンツを引きずり下ろすため民衆を率いて勃ちあがったのが、後の新日暮里共和国・初代 大統領ビリー・ヘリントンである。 ビリー氏とその仲間達の活躍をモチーフにしたゲイ術作品は数多いが、最も有名なのが、絵画『民衆を導く自由の裸神』で あろう。 今、COLTPLAYの曲と共に、一枚の絵画が漢たちの英雄譚を語り出す… 
------------
■世界性的 嘎七姆七樂隊COLTPLAY的新曲,是獻給在遙遠的過去,帝政末期的新日暮里實現市民革命的傳說的英雄們的生命贊歌。■在賢帝,石井王去世之後的動亂中 極力握住權力,極盡暴力之限的宰相TDN·コスギ。爲了脫下他的內褲而率領民眾起義的,就是之後新日暮里共和國首任總統Billy Herrington。以和Billy先生的那些朋友們為主題的Gay術作品有很多,最有名的,大概就是繪畫《引導人民的自由之裸神》吧。現在,和 COLTPLAY的曲子一起,用一幅繪畫把兄貴們的英雄故事娓娓道出......