ACM – 快速生成测试数据

比赛的时候出现了100 * 100组数据的情况,但是当时使用freopen忘记了具体的步骤,特意重新写一下,也是属于基础的内容。 生成一百行数据,每行100个数据,每个数据为100。 #include <stdio.h> #include <iostream>`enter code here` using namespace std; int main() { freopen("input", "r", stdin); freopen("output", "w", stdout); for(int i = ; i < 100; i++) for(int j = ; j < 100; j++) printf("%d%c", 100, j == 99? '\n' : ' '); fclose(stdin); fclose(stdout); return ; } 运行过后生成的数据(本来应该输出在屏幕上,此时不会输出到屏幕,而是输出到文件)会保存到output文件中。如果需要使用直接更改output的文件名,再使用一次freopen('r')即可。

Read More

ACM – 浙江省赛F – 图论

浙江省赛题目,分析后直接暴力即可,奈何场上脑子里全是floyd,WA无数次。 做题一定要先分析时间复杂问题,采取暴力方法,然后再考虑复杂问题解决方法。 此外今天开始使用赛用vimrc才发现出现不少问题,还好提前使用了。 #include <iostream> #include <stdio.h> #include <string.h> using namespace std; int n, m, k; const int maxn = 100 +10; int g[maxn][maxn]; void debug() { for(int i = ; i < n; i++) { for(int j = ;j < n;j ++) { cout << g[i][j]; } cout << endl; } } int main() { //freopen("input", "r", stdin); int t; cin >> t; int u, v; while(t--) { memset(g, , sizeof(g)); scanf("

Read More

ACM – 置换

终于搞明白置换了,可喜可贺。建议不要看屈的离散数学,看白书即可,通俗易懂。 我在这里简单阐述一下,当然也是依据李大大的书。 置换 置换就是把n个元素全排列,置换可以定义乘法。 循环就是置换的移位。例如: | 1 | 2 | 3 | 4 | 5 | | - | - | - | - | - | | 3 | 5 | 1 | 4 | 2 | 即为(1 3)(2 5)(4) 其中,(1 3)通过这个置换发现形成一个循环,(2 5)通过这个置换形成一个循环,(4)本身构成一个循环。 不动点 对于一个置换f,若一个着色方案s经过置换后不变,则称s为f的不动点,将f的不动点记录为C(f),则可证明等价类数目为所有C(f)的平均值,成为Burnside引理。 Polya定理 一般的,如果f分解成m(f)个循环的乘积,那么每个循环的所有格子的颜色必须相同。(因为这样才是一个不动点)。 假设涂k种颜色,则有 $$C(f) = k^{m(f)}$$ (乘法原理。循环内相同,循环间可以不同)。 代入Burnside引理之后得到Polya定理:等价类的个数等于所有置换f的$k^{m(f)}$的平均数。

Read More

ACM – 莫比乌斯反演

昨天卡了这道题目,今天特意来看看莫比乌斯反演。 其中,$∑_{d|n}$含义为整除. ACdreamer大大的讲解 看了这篇文章即可= = wikipedia的公式: 以上就是具体的公式,此外,还有线性筛法: void Init() { memset(vis,,sizeof(vis)); mu[1] = 1; cnt = ; for(int i=2; i<N; i++) { if(!vis[i]) { prime[cnt++] = i; mu[i] = -1; } for(int j=; j<cnt&&i*prime[j]<N; j++) { vis[i*prime[j]] = 1; if(i%prime[j]) mu[i*prime[j]] = -mu[i]; else { mu[i*prime[j]] = ; break; } } } } 这段代码也是摘自AC大大。我们得到这个东西有什么用? 简单来说,就是简化计算数论函数和的计算的过程,进行加速。 在HDU5212中,给出的题解是: 这道题需要一些莫比乌斯反演、线性筛的知识 定义$f(x)=x∗(x−1)$ 题目所求即为$\Sigma(f(gcd(ai,aj)|i!=j,1≤i,j≤n)$ 先用线性筛求出miu在[1,10000]的函数值 利用莫比乌斯反演公式我们可以$O(vlogv)$暴力求解出函数g(就是$f(n)/miu$)在[1,10000]的函数值,其中g满足: $\Sigma(g(d)|x)$ 这样所求答案即为: $\Sigma(g(d)∗cnt(d)∗cnt(d)|1≤d≤10000)$,其中cnt函数满足: cnt(x)=在a1,a2,..,an中是x的倍数的个数 而cnt的取值也可以$O(vlogv)$暴力计算出

Read More

ACM-zoj3789-排列利用

本文出自 利用排列找规律。 首先利用next_permutation函数进行求排列 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f int a[30]; int cal(int n) { int sum = ; int i; for (i = 1; i <= n; i++) { /* code */ sum = abs(sum - a[i]); } return sum; } void parray(int a[], int len) { int i; for (i = 1; i <= len; i++) { cout << a[i] << "

Read More

ACM-数据结构

{% blockquote 本文出自 http://svtter.com svtter.com %} 本文可以随意转载,但是转载请保留本信息. Uvaoj的判题效率不是很高。。所以直接开下一章节。题目慢慢刷,先过一遍书,不然书都看不完了TAT。。 6.1 栈和队列 卡片游戏,回顾了下队列和STL #include <stdio.h> #include <queue> #include <iostream> using namespace std; const int maxn = 100; int q[maxn]; void ace() { void ace2(int); int n; scanf("%d", &n); //init for(int i = ; i < n; i++) q[i] = i+1; int front , rear; front = , rear = n; // 队列不为空 while(front != rear) { printf("%d ", q[front++]); q[rear++] = q[front++]; } printf("

Read More

ACM-白皮书

本文出自svtter.com Pi的获取 觉得自己的一些ACMer的基本素养不够,重新翻看。 pi = 4.0 * atan(1.0) math.h中的M_PI并不是ANSI C标准。验证可以使用gcc -ansi scanf输入格式实验 之前阅读了scanf函数的相关部分(百科),但是依然没有很好的掌握。 现在依然没有= =。 有时间需要重新学习一下。 判断整数和浮点数大小 floor(m + 0.5) == m 通过+0.5来判断m的整数值。 floor/ceil是数学库里提供的函数,默认gcc不会自动链接math库, 方法是(-l + 库) gcc -Wall myround.c -lm -o myround 使用clock()计时 包含头文件time.h printf("Time used = %.2lf\n", (double)clock() / CLOCKS_PER_SEC); 会从程序开始的时候计时(不管输入输出),所以最佳方法是echo 数据 | ./a.out 多次使用clock()来计时的吧。。。 重定向和fopen读取文件输入测试数据 int main() { #ifdef LOCAL freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif } 添加编译选项:-DLOCAL, 使得中间部分生效.

Read More

ACM-白皮书-练习

本文出自svtter.com 基础第二弹 虽然是很水的题目,但是还是收获了不少。 动态小数位数 #include <stdio.h> #include <math.h> int main() { int a, b, c; while(~scanf("%d %d %d", &a, &b, &c)) { printf("%.*lf", c, a/(double)b); } return ; } 整数位数 // 整数位数 int cal(int a) { if(a == 0) return 0; return (int) log10( (double) a)+1; } 电灯 #include <stdio.h> #include <string.h> #define bool int //C语言没有bool bool light[1010]; //C也没有引用 void trans(bool *a) { if(*a) *a = ; else *a = 1; } int main() { int i, j; int n, k; while(~scanf("

Read More

ACM-白皮书3

本文出自svtter.com 整数进制输出 printf("%d %o %x\n", a); 把整数按照十进制,八进制和十六进制输出. $2^32-n$补码表示法. 字符处理 使用Ctrl+D时, getchar()读到的是-1 #include <stdio.h> #include <string.h> int main(int argc, const char *argv[]) { char c = getchar(); printf("%d%c\n", c, c); return ; } 假设一个年份为1993/12/12, 那么如何简单获取年月日? 使用sscanf函数. #include <stdio.h> #include <string.h> int main(int argc, const char *argv[]) { int year, month, day; char s[] = "1993/12/12"; sscanf(s, "%d/%d/%d", &year, &month, &day); printf("%d/%d/%d\n", year, month, day); return ; } 可以使用fgets(s, MAXN, stdin)来获取简单的输入.

Read More

ACM一个队伍的建成之我见

今天刷题数论题目的时候有所感想。 首先建立一支比较强悍的ACM队伍第一点就是保证刷题量,看再多的书,不做练习肯定是不行的。 选一本正确的指导教材,比如说李汝佳的白皮书,简单易懂,快捷粗暴,按照给出的分类进行训练,效果更佳。 正确的分类。ACM/ICPC的题目各个方向等等都有,各个都很精通对于大学才刚开始培养的acmer恐怕不是很现实,不如巩固共同部分,着重培养较为偏门的部分。最简单的方法也是通过分类,给学生一个兴趣方向,数论的可以顺带研究密码学等学科,对于以后的长远发展也是有很大的好处 — 反而,样样精通可能造成的结果就是样样不精通。当然,如果敏而好学,那么不局限于这一点。 想想去年这个时间在刷一份简单的模板,感觉用处实在是不大,问题都没有好好的理解。

Read More