本题惨状不可言表。

做完之后只见房间里Hack无数。Div.1那边更加激烈，某些人甚至Hack成功20次+

我的错误代码神奇的挺过了一次Hack。。。最终跪在了System Test上。

然后发现我的代码有两个问题。。。。。。。。。。

先来说下题目：

这道题的意思就是给你两个数，代表一个直角三角形的两条直角边。然后让你找到这个三角形，但是必须符合以下要求：

1. 三角形的三个点都在整点上。

2. 三角形的三条边都不能坐标轴平行。（←，我第一次就没有注意这一点，只判断了两条直角边不能与坐标轴平行）

我的解法是枚举两个点可能的坐标。要求产生a^2+b^2=c^2这样的一组数a, b，其中c是输入的其中一个数。

找到这个之后就可以构造三角形了。

另两个坑点是，需要判断第三条边是否平行于坐标轴，就是两个Y值不能相同。

另一个坑点是，有些数字产生的形如a^2+b^2=c^2的a和b不只有一组，所以需要都把它们弄下来。

最后我还是勉勉强强的通过了这题。。下面是AC代码（C#）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Threading.Tasks; 

namespace test05 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            new Solve().run(); 

            //Pause 
            //Remeber Comment it!!! 
            //Console.Write("==================nPause..."); Console.Read(); 
        } 
    } 
    class Solve 
    { 
        public void run() 
        { 
            string[] tempInput = Console.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); 
            int a = int.Parse(tempInput[0]); 
            int b = int.Parse(tempInput[1]); 

            List<int[]> ka = isright(a); 
            if (ka.Count == 0) 
            { 
                Console.WriteLine("NO"); 
                return; 
            } 
            List<int[]> kb = isright(b); 
            if (kb.Count == 0) 
            { 
                Console.WriteLine("NO"); 
                return; 
            } 

            foreach (int[] kaa in ka) 
            { 
                foreach (int[] kbb in kb) 
                { 
                    int temp; 
                    int a1 = kaa[0], a2 = kaa[1]; 
                    int b1 = kbb[0], b2 = kbb[1]; 
                    if (a1 > a2) 
                    { 
                        temp = a1; a1 = a2; a2 = temp; 
                    } 
                    if (b1 > b2) 
                    { 
                        temp = b1; b1 = b2; b2 = temp; 
                    } 

                    if (a1 * b2 == a2 * b1) 
                    { 
                        if (a1 != b2) 
                        { 
                            Console.WriteLine("YES"); 
                            Console.WriteLine("0 0"); 
                            Console.WriteLine(a2 + " " + a1); 
                            Console.WriteLine(-b1 + " " + b2); 
                            return; 
                        } 
                        else if (a2 != b1) 
                        { 
                            Console.WriteLine("YES"); 
                            Console.WriteLine("0 0"); 
                            Console.WriteLine(a1 + " " + a2); 
                            Console.WriteLine(-b2 + " " + b1); 
                            return; 
                        } 
                    } 
                } 
            } 
            Console.WriteLine("NO"); 
        } 
        List<int[]> isright(int a) 
        { 
            List<int[]> ans = new List<int[]>(); 
            for (int i = 1; i <= a; i++) 
            { 
                for (int j = 1; j <= a; j++) 
                { 
                    if (i * i + j * j == a * a) 
                    { 
                        ans.Add(new int[] { i, j }); 
                    } 
                } 
            } 
            return ans; 
        } 
    } 

} 

昨天这题System Testing跪了简直可惜。

原做法是把这个字符串从头循环到尾，然后去统计字母个数。

结果怎么出错的我也不知道。

我怎么总是在比赛的时候想不到正则表达式呢：

以下是AC代码（C#），程序主体就一行。。。

1
2
3
4
5
6
7
8
9

using System; 
using System.Text.RegularExpressions; 
class TaroString 
{ 
    public String getAnswer(String S) 
    { 
        return new Regex("^[^CAT]*C[^CAT]*A[^CAT]*T([^CAT]*)$").Match(S).Success ? "Possible" : "Impossible"; 
    } 
} 

顺便，其实昨天做出来两题，但是第2题也跪了。。。猜想错误，本来老老实实暴力就好。

第三题是个DFS+DP。。。当时没看出来。

总之就是HLL的得了0分。

专门发第一题代码的原因是。。。

以后记着正则表达式！！！明明你会用！！！

PS. 作为一个主要语言是C++的人，我在Codeforces上用PHP，在TopCoder用C#，真的大丈夫？

最近不知道是抽了什么风，可能是因为一不小心安装了VS2013，然后把默认语言选成了C#的原因。。。

总之是突然玩起了C#。。。

话说，C#是我最早接触到的编程语言之一。（我的第一门编程语言是ActionScript 2.0，最早接触到的是QBASIC，但是只照着源程序打，没有能记下来。）

大概是在高二的时候，为了做一个字符串处理的工作，开始学了C#，不过掌握的仅仅是输入输出，和字符串类的一些方法。

下面打一些代码片段：

Windows编程：

退出程序：Application.Exit();

最小化窗口：this.WindowState = FormWindowState.Minimized;

拖动控制（点击这个部分并拖动，可以起到拖动整个窗口的作用）：

1
2
3
4
5
6
7
8
9
10
11

[DllImport("user32.dll")] 
public static extern bool ReleaseCapture(); 
[DllImport("user32.dll")] 
public static extern bool SendMessage(IntPtr hwdn,int wMsg,int mParam,int lParam); 
public const int WM_SYSCOMMAND = 0x0112;//该变量表示将向Windows发送的消息类型 
public const int SC_MOVE = 0xF010;//该变量表示发送消息的附加消息 
public const int HTCAPTION = 0x0002;//该变量表示发送消息的附加消息 
private void Form1_MouseDown(object sender, MouseEventArgs e) { 
    ReleaseCapture(); 
    SendMessage(this.Handle, WM_SYSCOMMAND, SC_MOVE + HTCAPTION, 0); 
} 

给窗口添加阴影效果：

1
2
3
4
5
6
7
8
9
10
11
12

[DllImport("user32.dll")] 
public static extern int SetClassLong(IntPtr hwnd, int nIndex, int dwNewLong); 
[DllImport("user32.dll")] 
public static extern int GetClassLong(IntPtr hwnd, int nIndex); 
const int CS_DropSHADOW = 0x20000; 
const int GCL_STYLE = (-26); 
public MainPage() 
{ 
    InitializeComponent(); 
    //阴影效果添加在这里 
    SetClassLong(this.Handle, GCL_STYLE, GetClassLong(this.Handle, GCL_STYLE) CS_DropSHADOW); 
} 

子进程调用外部程序（无前台窗口显示）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Process proc = new Process(); 
proc.StartInfo.FileName = ftext[0];//要调用的外部程序名 
proc.StartInfo.Arguments = ftext[1];//程序参数 

//下面两行控制被调用程序不显示窗口，仅以子进程方式运行 
proc.StartInfo.CreateNoWindow = true;//不显示窗口执行哦 
proc.StartInfo.UseShellExecute = false;//不启用操作系统外壳进程 

//重定向标准输出 
proc.StartInfo.RedirectStandardOutput = true; 
this.Cursor = System.Windows.Forms.Cursors.WaitCursor;//在执行期间让鼠标变成小圈圈转起来。。。 
proc.Start(); 
//读出标准输出内容。（此处演示的是将输出内容放入richTextBox1中。 
using (StreamReader reader = proc.StandardOutput) 
{ 
    string thisline = reader.ReadLine(); 
    while (thisline != null) 
    { 
        richTextBox1.AppendText(thisline + "n"); 
        Application.DoEvents();//多线程执行（如果不加此句，在外部程序执行期间，主程序会假死） 
        thisline = reader.ReadLine(); 
    } 
} 
proc.WaitForExit();//等待子进程结束后执行以下的语句。 
this.Cursor = Cursors.Default; //子进程运行完毕，把鼠标改回原来的指针形状。 

注意，当外部程序标准输出过多的时候，可能造成缓冲区写满，此时外部程序会等待主程序读出缓冲区内容，再继续执行。但是主程序必须等待这个外部程序结束后才能继续，造成进程死锁。

解决方法1：将标准输出重定向到另一个文件，然后读那个文件。

解决方法2：（上面程序的解决方案）在proc.WaitForExit();之前就把标准输出读掉。如果处理比较简单，还可以一边读一边处理。

字符串处理：

返回一个字符串内部包含几个子串：

（假设字符串为S，子串为subS）

1

int c = S.Split(new[] { subS },StringSplitOptions.None).Length - 1; 

正则表达式匹配：

1

return new Regex("正则表达式字符串").Match(S).Success ? "Yes" : "No" ; 

某字符的首次出现位置：

1

return Str.IndexOf('N'); 

关于如何快速将java源程序转换成C#源程序：

以下是一段Java源程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import java.util.ArrayList; 

class GetPrime { 
    Integer[] getPrime(int n) { 
        ArrayList<Integer> prime = new ArrayList<>(); 
        boolean[] vis = new boolean[n + 1]; 
        for (int i = 2; i < n; i++) { 
            if (!vis[i]) 
            prime.add(i); 
            for (int p : prime) { 
                if (i >= n / p) 
                    break; 
                vis[i * p] = true; 
                if (i % p == 0) 
                    break; 
            } 
        } 
        return prime.toArray(new Integer[0]); 
    } 
} 

Integer转换成int

boolean转换成bool

ArrayList转换成List

然后还有一些细微修改就好了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

using System; 
using System.Collections.Generic; 

class GetPrime 
{ 
    public int[] getPrime(int n) 
    { 
        List<int> prime = new List<int>(); 
        bool[] vis = new bool[n + 1]; 
        for (int i = 2; i < n; i++) 
        { 
            if (!vis[i]) 
                prime.Add(i); 
            foreach (int p in prime) 
            { 
                if (i >= n / p) 
                    break; 
                vis[i * p] = true; 
                if (i % p == 0) 
                    break; 
            } 
        } 
        return prime.ToArray(); 
    } 
} 

关于以上程序里面其他细微的修改：在方法函数定义前增加了public，在第二个List的<>加入了变量名。

List添加方法改为了Add（只有大小写的变换），for改成了foreach，中间的冒号改成了in。
去掉了ToArray的参数。（在C#中，ToArray会自动推断类型，如果在泛型编程中，请这样写c.ToArray<int>();）

C#和java有着非常多的相似之处，而且据我这几天的使用感觉，C#在很多方面比java更好，而且微软MSDN的文档十分详细（还都是中文）。

嗯，这篇日志先写到这里。

后记：昨天用C#去玩了TopCoder，结果HLL的得了0分。。。。（其实就算不是C#，也会得0分。做出两题，排名前200，结果System Testing全跪。。。第一题是字符串最后一小段没处理好（←没用正则简直哭瞎），第二题是做出了错误的猜想，本来暴力就行的啊。。。）

摘要：我好无聊啊。。。。

众所周知，M67大神的博客首页有一个400个方块组成的16×25的版面。而且是实时刷新的。于是，长期以来，这块分辨率只有16×25的场所就成了众Geek的娱乐之地。

但是，我每次浏览M67博客主页的时候，这些方块不能组成规则的图形。这绝对不是我这种强迫症的风格。 如何快速在M67博客主页的16×25的方块阵上建立一个图形呢？

我查看了M67主页源码。发现所有的方块变色操作只有一个函数inverse控制，这个函数接受一个1~400的整型参数，表示位置。执行后该位置上颜色会反转。在此基础上，我们可以用一段代码控制，判断图形中哪些块需要反转并只对这些需要反转的块执行inverse函数。

以下是一些图案：​

全黑（填上数组形成黑底图案）：

1

(function(){img=[];for(i=1;i<=400;i++){var iru=0;var x=document.getElementById("td"+i);len=img.length;for(j=0;j<len;j++){if(img[j]==i)iru=1}if((iru==0)&&(x.bgColor=="#FFFFFF"))inverse(i);else if((iru==1)&&(x.bgColor=="#404040"))inverse(i)}})(); 

全白（填上数组形成白底图案）：

1

(function(){img=[];for(i=1;i<=400;i++){var iru=0;var x=document.getElementById("td"+i);len=img.length;for(j=0;j<len;j++){if(img[j]==i)iru=1}if((iru==0)&&(x.bgColor=="#404040"))inverse(i);else if((iru==1)&&(x.bgColor=="#FFFFFF"))inverse(i)}})(); 

全部反转：

（我记得这个功能以前直接有按钮来着，现在M67怎么去掉了？）

1

(function(){for(i=1;i<=400;i++)inverse(i);})(); 

心形：

1

(function(){img=[84,85,90,91,108,109,110,111,114,115,116,117,132,133,134,135,136,139,140,141,142,143,157,158,159,160,161,162,163,164,165,166,167,168,182,183,184,185,186,187,188,189,190,191,192,193,208,209,210,211,212,213,214,215,216,217,233,234,235,236,237,238,239,240,241,242,259,260,261,262,263,264,265,266,285,286,287,288,289,290,311,312,313,314,337,338];for(i=1;i<=400;i++){var iru=0;var x=document.getElementById("td"+i);len=img.length;for(j=0;j<len;j++){if(img[j]==i)iru=1}if((iru==0)&&(x.bgColor=="#FFFFFF"))inverse(i);else if((iru==1)&&(x.bgColor=="#404040"))inverse(i)}})(); 

下面我只发数字咯：

π：

1

108,109,110,111,112,113,114,115,116,133,134,135,136,137,138,139,140,141,161,163,186,188,210,211,213,235,239,258,259,260,264,283,284,290,291 

游戏机手柄：

1

55,56,80,81,103,104,105,106,107,108,128,129,130,131,132,133,155,156,180,181,210,211,214,215,117,118,120,121,142,143,145,146 

马里奥：

1

10,11,12,13,14,34,40,41,42,58,68,83,84,85,88,90,91,92,107,110,111,113,118,132,135,136,139,143,158,159,163,164,165,166,167,183,184,185,191,206,207,211,212,215,216,217,230,237,238,241,243,255,261,262,263,264,265,266,269,281,284,285,286,287,289,290,292,294,307,308,309,310,311,312,313,314,315,316,318,331,334,335,336,337,338,339,340,343,356,360,363,367,382,383,384,389,390,391 

猫咪：

1

33,43,57,59,67,69,81,83,85,91,93,95,105,106,108,110,111,112,113,114,115,116,118,120,121,129,147,153,173,178,180,181,182,183,193,194,195,196,198,203,223,228,231,232,244,245,248,253,256,257,269,270,273,278,288,298,303,309,312,314,317,323,329,335,336,340,341,347,355,356,371,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395 

史努比：

1

11,12,13,14,15,35,41,42,59,67,68,82,83,84,85,88,93,94,105,106,107,110,113,119,120,130,145,155,157,158,170,180,182,183,195,205,220,230,231,233,238,245,257,258,259,260,261,262,266,267,268,269,270,284,285,286,289,290,291,293,294,311,314,317,318,335,336,339,360,364,365,384,390,391 

黑白格：

1

(function(){img=[];for(i=1;i<=400;i++){var iru=0;var x=document.getElementById("td"+i);len=img.length;if(i%2==0)iru=1;if((iru==0)&&(x.bgColor=="#404040"))inverse(i);else if((iru==1)&&(x.bgColor=="#FFFFFF"))inverse(i)}})(); 

图案转img数组：（在控制台中执行）

1

(function(){var result="";for(i=1;i<=400;i++){var x=document.getElementById("td"+i);if(x.bgColor=="#404040")result=result+i+",";}console.log(result);})(); 

代码是直接复制到浏览器地址栏执行即可。。。有些浏览器可能吞“javascript:”，自己手动加上就好。

嗯，我就贴一张图。。。

新年第一次更新——

bilibili拜年祭如期在大年三十晚上发布了，B站又陪着我们过了一年。

我仔细分析了一下，发现了一个十分神奇的播放器调用参数as_wide=1。于是经过研究，我发现这个参数是B站播放器默认宽屏的参数。

想当年做bilibili播放器嵌入的时候我就想是不是存在这样一个参数，我还自己猜测可能的参数，没想到是as_wide呀。

所以我把这个参数也应用到这里了，使用代码调用B站播放器的时候，播放器展示的大小和样式我也调整过了。

以及另外一堆很细微的更改。比如替换使用的正则表达式更准确。

增加兼容性——有B站cookie，调用B站站内播放器。无B站cookie，自动回落至站外播放器。（←这一切都在浏览器端完成，判断也是由B站网页进行的，无需担心账号泄露）

这次就应该算是完美嵌入了。。。不过还是有不完美的地方的。。比如网页全屏还是没法用，比如我的API权限不够高，不要说里世界了，连有些会员的世界的cid都取不到。

下面是本次修改之后的测试：LoveLive 6th single 《Music S.T.A.R.T!!》

av847544p1

最近彻底入了Lovelive的大坑。。。作为一个冲着南条爱乃和三森铃子这两个CV去看动画的人来说。。。。看完之后我喜欢上了果果。。。。

嗯，Lovelive也是4月就有第二季了。说起来，4月值得期待的动画还真多。

本文是我在 果壳网 对于 【NPAPI插件是指？為何屏蔽呢？安全？卡死？崩溃？影響有多大呢？】 问题的回答，原帖见此处。

最近，Google宣布将屏蔽NPAPI插件，Firefox也开始在其应用商店中移除基于NPAPI的插件，为何屏蔽NPAPI插件，对我们有什么影响呢？

摘要

——写给那些“太长不看”的人们

NPAPI是上世纪末由网景（Netscape）开发的一套浏览器插件应用程序接口，它允许浏览器调用外部应用程序。

由于NPAPI的架构太老，存在安全性问题，难以维护，用户体验不好等种种原因，再加上现在有了HTML5这个替代品，以及不支持移动平台等原因，NPAPI插件已经开始退出历史舞台。

除了少数运行在Chrome、Firefox上的网银插件之外，你绝大部分的网络操作不会受到任何影响，现在早已不是NPAPI的世界了。

再说，人家只是屏蔽，还没到不支持的程度，你还可以手动开启嘛。

============================我是一条普通的分割线============================

以下为正文：

NPAPI是什么？

所谓NPAPI，就是指网景插件应用程序接口（Netscape Plugin Application Programming Interface）[1][2]，是一种外部程序作为插件和浏览器共同完成网页展示的调用通道。

这么说可能很难理解。。。。那么我换一种表达方式。。我们在写网页的时候，在html中插入的<object></object>或是<embed></embed>标签 ，实际上就声明了一种在网页中调用其他插件的方法。

我们的浏览器中存在许多NPAPI插件

再或者说。。。我们浏览器中的外部播放器（音频、视频）、PDF阅读器、网银助手、X宝安全助手、XX下载管家这些东西，都是NPAPI插件。

这东西有什么用？

由于前期Mozilla的大力推动[3]，加上微软的ActiveX表现实在太差[4]，所以在相当长的一段时间里，（其实直到现在也是一样）绝大多数浏览器插件都是NPAPI开发的，而NPAPI也支持绝大部分的浏览器[2]，除了IE那个异类[5]。。。。。。

对于用户来说，插件（plugin）允许更多样式的内容在浏览器中运行，支持一些浏览器未定义的行为和MIME类型。比如在浏览器中打开音乐，要使用音乐播放器——我记得我高中信息课上，初学网页制作，那时老师讲到，在网页里插入一个音频要使用<embed>标签，浏览器会自动调用Windows Media Player运行——就像这样，对用户来说，插件就相当于运行在网页上的应用程序。

（↑ 注意，这和扩展（extension）不一样，扩展本身也是网页）

NPAPI哪里不好了？

不过，随着Web的发展、浏览器的强大、HTML5席卷全球，Javascript的功能已然逆天，甚至可以操控硬件[6]，做算法竞赛的题目[7]。。。。。。这种时候，plugin本身的缺陷就显示出来了。 其实早在2011年，就有报道[8]指出以Adobe Flash Shockwave为首的浏览器插件是导致浏览器安全漏洞的最大原因。直到最近的统计中[9]，仍能看到这种趋势。

由于运行插件的本质就是调用外部程序，将外部程序产生的输出写回浏览器中。这个把本应该在浏览器内部的数据向外发送的过程，就容易引起安全问题。

不仅是安全问题，NPAPI还有很多为人诟病的问题，首先是它用户体验极差。。。在登录网站的时候被要求安装插件这种感觉并不是十分好，尤其是对于很多电脑技术并不好的人来说，安装插件本身就不是容易的事情。 其次，还有插件的跨平台性不好[10]，除了java外，其余的插件基本只能在单一的平台上运行 ，而移动时代的来临也使得Windows一家独大的时代受到了挑战——明显的，这些NPAPI插件很少能在移动端运行起来。

HTML5技术的快速发展，越来越多以前需要外部程序实现的操作，变得现在可以由浏览器直接实现。从音频、视频的播放，到使用电脑的摄像头、麦克风，从访问用户文件到远程会议[11]……更重要的是，通过HTML5和Javascript，这些东西变得标准化。对于开发者，不需要再编写复杂的代码来完成这些功能，而且并不用考虑为不同的平台开发不同的系统。对于用户，浏览器能做更多的事情，不仅方便，而且更加安全。

从网页视频播放器来说，几年前，flash播放器占绝对统治地位，HTML5播放器很难超越[12]。如今的Youtube，你已经很少能看到flash播放器，HTML5播放器已经成了默认的视频播放器。

正因如此，NPAPI已经是过时的架构，而新技术已经足够成熟足以替代老产品，让它退出历史舞台。

作为用户，NPAPI没了，我会有什么影响呢？
如果浏览器没了NPAPI。。。。。。事实上不会产生太大影响，因为根据统计[10]，我们平常浏览网页使用的插件就那么几个，大多数用户可能一个插件都没有。 不过在中国，可能是另外一种样子，因为很明显的，现在所有的安全插件都不能用了，包括X宝的安全插件和各大网银。

HTML5技术发展到了今天，是该有一次这样的革新，让老标准彻底下台了。虽然对于各大网银可能很痛苦（“我们刚刚支持的Chrome，你TM告诉我不能用了？”），不过好在国内用户大多有开IE上网银的习惯（苦笑），所以停用NPAPI也是我们应该支持的。

还有，无论是Chrome还是Firefox，在其发布的声明中也只是说“屏蔽”，并未表示要彻底停止对NPAPI的支持。 作为例子，Java插件由于安全性问题，很早就已经默认屏蔽了。 所以说，在这之后的NPAPI插件，仍然可以通过手动开启。

作为开发者，NPAPI没了，我该怎么继续开发插件呢？

我觉得现在开发插件是没有前途的（←地图炮开启）！HTML5已经可以实现很多以前难以想象的功能了，可能很少有HTML无法做到的东西。再加上移动平台的大热，传统插件之后的路，我也是不看好的。

现在移动平台、云计算这些仍然是热门，开发纯云端应用、纯Web应用是个不错的选择，用户访问你的网址之后，应用就能直接在浏览器里运行，像是云端办公、云端图像处理、云端转码等应用使用量都在不断上升。

开发浏览器扩展来替代原来的插件。和插件不同，浏览器扩展本身也是网页，运行在浏览器内部，是个相对安全的环境。

以上都需要HTML5技术，而今天的HTML5技术，已经完完全全足够各种各样应用的开发，我认为在这方面，是不应该有顾虑的。

总结

其实没什么好总结的，和ActiveX一样，NPAPI也是过时的技术，现在的消失是正常的事情。不依赖外部程序，仅仅浏览器就能做到的事情已经非常多了，如果你不是NPAPI插件的开发者，这件事不会对你造成影响。

本来，计算机技术的发展就是一天一个样，我们总能用到最好的东西就行了，你说是不？

关于知识产权及引用：

本文采用知识共享协议CC BY-NC-ND 4.0，协议全文请点击此链接。

如果你也想使用这张图片，请点击 这里。

参考资料和引用来源：

• [1] http://zh.wikipedia.org/wiki/NPAPI
• [2] http://en.wikipedia.org/wiki/NPAPI
• [3] http://news.cnblogs.com/n/108581/
• [4] 我懒的去找来源，大家都懂的。。。
• [5] http://support.microsoft.com/kb/306790/zh-cn
• [6] http://www.csdn.net/article/2012-07-15/2807348
• [7] http://codeforces.com/blog/entry/79
• [8] http://tech.sina.com.cn/i/2011-05-23/11535558297.shtml
• [9] http://www.oschina.net/news/46493/browser-plugins-security
• [10] http://www.cnbeta.com/articles/253889.htm
• [11]http://zh.wikipedia.org/wiki/WebRTC
• [12] http://www.cnbeta.com/articles/115393.htm

树状数组（Binary Indexed Trees， BIT， 二分索引树），是一种方便的处理前缀和的特殊的数据结构。

使用树状数组的好处就是它可以在O(log n)的时间内计算前缀和，并且可以在O(log n)的时间内更新数组中的某个值。

树状数组的实现依赖二进制的特殊性质，把一个前缀和分成若干个子序列的和，平均了查找和更新所需要的操作次数来达到这个目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/*************************************** 
* * 
* Template of Binary Indexed Tree * 
* * 
* @author: Zyzsdy * 
* * 
**************************************** 
* Thanks: shu_mj * 
* ACM Template of Tokyo U * 
***************************************/ 
template <class Type> 
struct binaryIndexTree { 
    Type *data; 
    int size_n; 
    binaryIndexTree (int _size) : size_n (_size + 1) { 
        data = new Type[size_n](); 
    } 
    ~binaryIndexTree() { 
        delete [] data; 
    } 
    void add (int _lower, Type _delta) { 
        int pos = _lower + 1; 
        while (pos < size_n) { 
            data[pos] += _delta; 
            pos += pos & -pos; 
        } 
    } 
    Type sum (int _lower, int _upper) { 
        if (_lower > 0) { 
            return sum (0, _upper) - sum (0, _lower); 
        } else { 
            Type result = 0; 
            int pos = _upper; 
            while (pos > 0) { 
                result += data[pos]; 
                pos -= pos & -pos; 
            } 
            return result; 
        } 
    } 
}; 
typedef binaryIndexTree<int> BIT; 

这份树状数组模板支持自动根据数据类型和数据量申请内存，单点更新和区间查询。就算不用模板，这份代码也很容易记忆。。

下面是HDU 1166，典型的树状数组题目，直接套上面的模板就可以解了。。因此不再放出完整代码，只贴上主函数，复制这两份代码再添上头文件即可运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

int main(int agrc, char *agrv[]) { 
    int T; 
    scanf("%d",&T);
    for(int i=1;i<=T;i++){ 
        printf("Case %d:n",i); 
        int n; 
        scanf("%d",&n); 
        BIT *ps=new BIT(n); 
        for(int j=0;j<n;j++){ 
            int p; 
            scanf("%d",&p); 
            ps->updateDelta(j,p); 
        } 
        char buff[80]; 
        while(true){ 
            scanf("%s",buff); 
            if(buff[0]=='E') break; 
            int posi,shuj; 
            switch(buff[0]){ 
                case 'Q': 
                    int l,r; 
                    scanf("%d%d",&l,&r); 
                    printf("%dn",ps->sum(l-1,r)); 
                    break; 
                case 'A': 
                    scanf("%d%d",&posi,&shuj); 
                    ps->updateDelta(posi-1,shuj); 
                    break; 
                case 'S': 
                    scanf("%d%d",&posi,&shuj); 
                    ps->updateDelta(posi-1,-shuj); 
                    break; 
            } 
        } 
        delete ps; 
    } 
} 

什么都不说了。

http://codeforces.com/contest/382/submission/5728990

因为比赛的时候被坑了，所以我写了特别详尽的注释。。。

直接看代码就好。。。

我是不是应该放弃使用PHP来打CF？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

<?php 
# 输入处理 
# 读入第1行，并丢弃 
$in=fgets(STDIN); 
# 读入第2行 
$in=fgets(STDIN); 
# 按空格分隔并转换为整数 
$num=explode(" ", $in); 
foreach ($num as &$v) { 
    $v=intval($v); 
} 
# $len 存储数据个数 
$len=count($num); 
# 输入处理结束 

# 当只有0或1个数字的时候，输出-1并退出 
if($len<=1){ 
    echo -1; 
    exit(); 
} 

# 预处理 
# 将 $num 数组按升序排列 
sort($num); 
# 建立空数组 $error，用以存放两数差值 
$error=array(); 
# 分别计算数组中前后两数差值，以这个差值为键，存入$error中。 
for($i=1;$i<$len;$i++){ 
    # 计算当前数和之前数的差值 
    $ds=$num[$i]-$num[$i-1]; 
    # 如果存在这个差值，就把当前下标插入这个差值所在的数组中。 
    if(array_key_exists($ds, $error)){ 
        array_push($error[$ds],$i); 
    # 否则，新建这个差值为键，下标为值的数组 
    }else{ 
        $error[$ds]=array($i); 
    } 
} 
# 统计存在的差值个数 
$errorcount=count($error); 
# 预处理结束 

# 结果处理 
# 新建结果数组 
$result=array(); 
# 对存在的差值个数进行分类讨论 
# 如果差值个数小于或等于0 
if($errorcount<=0){ 
    # 你TM在逗我？ 
    exit(); 
}else 
# 如果只有一个差值——可能情况： 
# 1.只有2个元素； 
# 2.已经是等差数列； 
if($errorcount==1){ 
    # 检出这个差值，保存在 $d 中 
    $d=array_keys($error); 
    $d=(int)$d[0]; 
    # 如果只有两个元素 
    if($len==2){ 
        # 检查是否可以在中间插入 
        if($d%2==0) 
        array_push($result, $num[1]-$d/2); 
    } 
    # 对于已经是等差数列的情况和只有两个元素的情况，都需要两边插入 
    array_push($result, $num[0]-$d, $num[$len-1]+$d); 
    # 去除结果数组中重复数据 
    $result=array_unique($result); 
    # 对结果数组再排序 
    sort($result); 
    # 输出 
    echo count($result); 
    echo "n"; 
    foreach ($result as $v) { 
        echo $v." "; 
    } 
    exit(); 
}else 
# 如果存在两个差值，则有可能存在一个 
if($errorcount==2){ 
    # 检出这两个差值 
    $d=array_keys($error); 
    sort($d); 
    # 检查较大的key是否是较小的key的2倍 
    if($d[1]-$d[0]==$d[0]) { 
        # 如果是，则检查较大的key是否只有一个元素。 
        if(count($error[$d[1]])==1){ 
            # 如果是，则在此键值处插入 
            $result=$num[$error[$d[1]][0]]-$d[0]; 
            # 输出 “1n此数字” 
            echo "1n".$result; 
            exit(); 
        } 
    } 
    # 否则，输出0 
    echo 0; 
    exit(); 
} 
# 如果存在多于两个差值，则一定不存在可插入元素 
else{ 
    # 输出0 
    echo 0; 
    exit(); 
} 
?> 
<!doctype html> 
<html> 
    <head> 
        <title>Zyzsdy</title> 
    </head> 
    <body> 
        <p>这数据也太坑了。。。。</p> 
        <p> </p> 
        <p>@author: Zyzsdy</p> 
        <p>@Website: <a href="http://www.namido.net" target="_blank">http://www.namido.net</a></p> 
        <p>@date: 2014/1/18 15:02 (UTC+8)</p> 
        <p> </p> 
        <p>感想： 这次CF就过一题居然没扣分。。。。。。</p> 
        <p>不过我这题差一点就做出来了。。。</p> 
        <p>。。。。。。。</p> 
        <p>唉。。。。</p> 
    </body> 
</html>