ACM – hdu5104-water

这个题目的总结就是不作不会死- -好端端的暴力我非要用个bfs。

看见自己wrong了还以为是哈希的问题- =

题意

  • p1+p2+p3 = n,$p1 <= p2 <= p3$
  • 输出符合条件的组数

输入输出

  • 给100组n,输出组数

分析

  • 只有3个数,暴力解就可以,注意循环终止条件。

Read More

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