Parabola意识流博客

NOI2001（All solved）

• chain http://ideone.com/n2lzi
• cannon http://ideone.com/F9P8U
• arctan http://ideone.com/suQCI
• clever http://ideone.com/ds1bE
• equation http://ideone.com/HKhw4
• secert http://ideone.com/dCjnf

NOI2002（All solved）

• galaxy http://ideone.com/vUQEP
• dragon http://ideone.com/ZiBw2
• robot http://ideone.com/1S4nb
• savage http://ideone.com/EGm5x

NOI2003

• hookey http://ideone.com/V2Bwo
• game http://ideone.com/Iyi5p
• editor http://ideone.com/Uot3R

NOI2004（All solved）

• manhattan http://ideone.com/ES9xo
• hut http://ideone.com/PvjZW
• rainfall http://ideone.com/w37Ya
• cashier http://ideone.com/wBIO8

NOI2005

• sequence http://ideone.com/2glHa
• adv1900 http://ideone.com/KsOAm
• lemon http://ideone.com/wWjvO
• cchkk http://ideone.com/5gv67

NOI2006

• profit http://ideone.com/TnlRS
• bag http://ideone.com/ocMqB

NOI2007

• network http://ideone.com/swAoc
• necklace http://ideone.com/ah1Fc
• cash http://ideone.com/KKrBm

NOI2008

• party http://ideone.com/0NrSY
• employee http://ideone.com/7i9K9

NOI2009

• poetg http://ideone.com/t4R90
• ball http://ideone.com/n4gvn
• pvz http://ideone.com/lgBfh
• transfrom http://ideone.com/Wa8IZ

NOI2010

• plane http://ideone.com/4Il3k
• altitude http://ideone.com/Ymr2J
• piano http://ideone.com/cy5aO
• energy http://ideone.com/H4pUn

NOI2011

（聪明的读者一看就知道这明明是11年 >_,<）

A*2012，是如此的坑爹，当然我很弱是一个原因。

复赛没交一题……我还能说什么呢……考挂自己弱吧……比赛结束后15min，把round2b C的样例调出来了

round2b啊2b啊2b啊……

/*
* Copyright (C) 2012 All rights reserved.
* File name:  C.cpp
* Author:     Parabola_ds
* Creat time: 2012.06.17
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <vector>
#include <cstdio>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define rep(i, n) for(int i = 1; i <= n; ++i)
using namespace std;

const int inf = ~0U >> 1;

set<int> n;
char bd[600];
int maxl, len, space, t;
long long num;
bool tt[600];

void ps(){ rep(i, space) printf(" "); }

int S[600];

void solve(){
	space = 4;
	int m = 0, fst = 0;
	int num;
	for(int i = 0; i <= maxl;){
		int j, tmp;
		bool bl;
		m++;
		switch(bd[i]){
			case '3':
				fst++;
				ps(); printf("for (int r%d = 0; r%d < ", fst - 1, fst - 1);
				num = 0;
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				for(; bd[j] >= '0' && bd[j] <= '9' && j <= maxl; ++j)
					num = num * 10 + bd[j] - '0';
				printf("%d; r%d++)", num, fst - 1);
				if(tt[m]) printf(" {");
				puts("");
				space += 4;
				i = j + 1;
				break;
			case '2':
				ps(); printf("if (");
				num = 0; bl = bd[i + 1] == '#';
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				for(; bd[j] >= '0' && bd[j] <= '9' && j <= maxl; ++j)
					num = num * 10 + bd[j] - '0';
				if(bl) printf("r%d ", num); else printf("%d ", num);
				i = j + 1;
				if(bd[i] == '1') printf("== "); else if(bd[i] == '2') printf("< "); else printf("> ");
				num = 0; bl = bd[i + 1] == '#';
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				for(; bd[j] >= '0' && bd[j] <= '9' && j <= maxl; ++j)
					num = num * 10 + bd[j] - '0';
				if(bl) printf("r%d ", num); else printf("%d ", num);
				i = j + 1;
				break;
			case '1':
				ps();
				num = 0; bl = bd[i + 1] == '#';
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				for(; bd[j] >= '0' && bd[j] <= '9' && j <= maxl; ++j)
					num = num * 10 + bd[j] - '0';
				if(bl) printf("r%d =", num);
				i = j + 1;
				num = 0; bl = bd[i] == '#';
				j = i + (bd[i] == '#' ? 1 : 0);
				for(; bd[j] >= '0' && bd[j] <= '9' && j <= maxl; ++j)
					num = num * 10 + bd[j] - '0';
				if(bl) printf(" r%d ", num); else printf(" %d ", num);
				i = j + 1;
				if(bd[i] == '1') printf("+"); else if(bd[i] == '2') printf("-"); else if(bd[i] == '3') printf("*"); else printf("/");
				tmp = i;
				num = 0; bl = bd[i + 1] == '#';
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				for(; bd[j] >= '0' && bd[j] <= '9' && j <= maxl; ++j)
					num = num * 10 + bd[j] - '0';
				if(bl) printf(" r%d;\n", num); else printf(" %d;\n", num);
				i = j + 1;
				break;
			case '0':
				space -= 4;
				i++;
				fst--;
				if(tt[m]) ps(), printf("}\n");
				break;
		}
	}
}

int main(){
	cin.getline(bd, 600);
	len = strlen(bd);
	int m = 0, fst = 0;
	for(int i = 0; i < len;){
		int j, tmp;
		bool bl;
		m++;
		switch(bd[i]){
			case '3':
				S[++fst] = m;
				num = 0; bl = bd[i + 1] == '#';
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				if(j >= len){
					maxl = i; goto st;
				}
				maxl = j;
				for(; bd[j] >= '0' && bd[j] <= '9'; ++j){
					num = num * 10 + bd[j] - '0';
					if(num < inf) maxl = i; else{
						if(bl) n.insert(num);
						goto st;
					}
				}
				if(bl) n.insert(num);
				if(bd[j] != '*')
					goto st;
				maxl = j;
				i = j + 1;
				break;
			case '2':
				num = 0; bl = bd[i + 1] == '#';
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				if(j >= len){
					maxl = i; goto st;
				}
				maxl = j;
				for(; bd[j] >= '0' && bd[j] <= '9'; ++j){
					num = num * 10 + bd[j] - '0';
					if(num < inf) maxl = i; else{
						if(bl) n.insert(num);
						goto st;
					}
				}
				if(bl) n.insert(num);
				if(bd[j] != '*')
					goto st;
				maxl = j;
				i = j + 1;
				if(bd[i] < '1' || bd[i] > '3')
					goto st;
				maxl = i;
				num = 0; bl = bd[i + 1] == '#';
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				if(j >= len){
					maxl = i; goto st;
				}
				maxl = j;
				for(; bd[j] >= '0' && bd[j] <= '9'; ++j){
					num = num * 10 + bd[j] - '0';
					if(num < inf) maxl = i; else{
						if(bl) n.insert(num);
						goto st;
					}
				}
				if(bl) n.insert(num);
				if(bd[j] != '*')
					goto st;
				maxl = j;
				i = j + 1;
				break;
			case '1':
				num = 0; bl = bd[i + 1] == '#';
				if(!bl){
					maxl = i;
					goto st;
				}
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				if(j >= len){
					maxl = i; goto st;
				}
				maxl = j;
				for(; bd[j] >= '0' && bd[j] <= '9'; ++j){
					num = num * 10 + bd[j] - '0';
					if(num < inf) maxl = i; else{
						if(bl) n.insert(num);
						goto st;
					}
				}
				if(bl) n.insert(num);
				if(bd[j] != '*')
					goto st;
				maxl = j;
				i = j + 1;
				num = 0; bl = bd[i] == '#';
				j = i + (bd[i] == '#' ? 1 : 0);
				if(j >= len){
					maxl = i; goto st;
				}
				maxl = j;
				for(; bd[j] >= '0' && bd[j] <= '9'; ++j){
					num = num * 10 + bd[j] - '0';
					if(num < inf) maxl = i; else{
						if(bl) n.insert(num);
						goto st;
					}
				}
				if(bl) n.insert(num);
				if(bd[j] != '*')
					goto st;
				maxl = j;
				i = j + 1;
				if(bd[i] < '1' || bd[i] > '4')
					goto st;
				tmp = i;
				num = 0; bl = bd[i + 1] == '#';
				j = i + (bd[i + 1] == '#' ? 2 : 1);
				if(j >= len){
					maxl = i; goto st;
				}
				maxl = j;
				for(; bd[j] >= '0' && bd[j] <= '9'; ++j){
					num = num * 10 + bd[j] - '0';
					if(num < inf) maxl = i;
					if(num < inf) maxl = i; else{
						if(bl) n.insert(num);
						goto st;
					}
				}
				if(bl) n.insert(num);
				if(bd[tmp] == 4 && !num){
					maxl = tmp;
					goto st;
				}
				if(bd[j] != '*')
					goto st;
				maxl = j;
				i = j + 1;
				break;
			case '0':
				maxl = i++;
				if(m - S[fst] > 2) tt[S[fst]] = tt[m] = 1;
				fst--;
				break;
		}
	}
st:{}
	printf("%d\n", maxl + 1);
	printf("int main() {\n");
	for(set<int>::iterator it = n.begin(); it != n.end(); ++it)
		printf("    int r%d = 0;\n", *it);
	solve();
	printf("    printf(\"");
	set<int>::iterator it = n.begin();
	if(it != n.end()) printf("%%d"); it++;
	for(; it != n.end(); it++)
		printf(" %%d");
	printf("\"");
	for(it = n.begin(); it != n.end(); it++)
		printf(", r%d", *it);
	printf(");\n    return 0;\n}\n");
	return 0;
}

附题目（

    这题是用来防Ak的我一开始就跑去写干嘛啊！！！！！！！！！！！！！！！！！！！！！！！

    有点若菜的自我修养就不行么！！！！！！！！！！！！！！！！！！！！！

）：

 [tex]Calculate \sum_{1\le i<j\le n}{\gcd(i,j)}.\\ \begin{align*}&\sum_{1\le i<j\le n}{\gcd(i,j)}\\=&\sum_{1\le i<n}{\sum_{i<j\le n}{\gcd(i,j)}}\\=&\sum_{1<i\le n}{\sum_{1\le j<i}{\gcd(i,j)}}\\=&\sum_{1\le i\le n}{\sum_{d\mid i}{d\varphi(\frac{i}{d})}}.\end{align*}\\O(n\sqrt{n})~or~O(n\log{n}).\\ \begin{align*}=&\sum_{1\le d\le n}{\sum_{1\le i\le \frac{n}{d}}{\varphi(i)}}\\=&\sum_{1\le d\le n}{Sum\varphi_{\frac{n}{d}}}.\end{align*}\\O(n).\\ \begin{align*}d\rightarrow \frac{n}{\frac{n}{d}}.\end{align*}\\O(\sqrt{n}).\\ \begin{align*}for(x,y)=1,\\&(\sum_{x\mid n}{x\varphi(\frac{n}{x})})(\sum_{y\mid n}{y\varphi(\frac{n}{y})})\\=&\sum_{xy\mid n}{xy\varphi(\frac{n}{xy})}.\end{align*}\\O(1).[/tex]

注意……以上默认[tex]\varphi(1)=0[/tex]……然后就是上面的所有时间复杂度……均指询问复杂度……预处理的话可以线性，参考欧拉筛法。