1.统计数字
题目描述 Description
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数
不超过10000 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统
计结果。
输入描述 Input Description
第1行是整数n，表示自然数的个数。
第2~n+1 行每行一个自然数。
输出描述 Output Description
输出包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大
的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
样例输入 Sample Input
8
2
4
2
4
5
100
2
100
样例输出 Sample Output
2 3
4 2
5 1
100 2
数据范围及提示 Data Size & Hint
【限制】
40%的数据满足：1<=n<=1000
80%的数据满足：1<=n<=50000
100%的数据满足：1<=n<=200000，每个数均不超过1 500 000 000（1.5*10^9）
（来自http://codevs.cn/problem/1164/）
这道题没有什么特别的技术含量，排个序，再统计就行了
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cctype>
#include<map>
#include<set>
using namespace std;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
}
int n;
int* list;
int main(){
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
readInteger(n);
list = new int[(const int)(n + )];
for(int i = ; i < n; i++){
readInteger(list[i]);
}
sort(list, list + n);
int counter = ;
int last = list[];
for(int i = ; i < n; i++){
if(list[i] != last){
cout<<last<<" "<<counter<<endl;
last = list[i];
counter = ;
}else counter++;
}
cout<<last<<" "<<counter<<endl;
return ;
}
统计数字
2.矩阵取数游戏
题目描述 Description
【问题描述】
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m 的矩阵，矩阵中的每个元素aij均
为非负整数。游戏规则如下：
1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分= 被取走的元素值*2i，
其中i 表示第i 次取数（从1 开始编号）；
4. 游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入描述 Input Description
第1行为两个用空格隔开的整数n和m。
第2~n+1 行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
输出描述 Output Description
输出 仅包含1 行，为一个整数，即输入矩阵取数后的最大得分。
样例输入 Sample Input
2 3
1 2 3
3 4 2
样例输出 Sample Output
82
数据范围及提示 Data Size & Hint
样例解释
第 1 次：第1 行取行首元素，第2 行取行尾元素，本次得分为1*21+2*21=6
第2 次：两行均取行首元素，本次得分为2*22+3*22=20
第3 次：得分为3*23+4*23=56。总得分为6+20+56=82
【限制】
60%的数据满足：1<=n, m<=30, 答案不超过10
100%的数据满足：1<=n, m<=80, 0<=aij<=1000
（来自http://codevs.cn/problem/1166/）
这道题首先一看数据范围就知道要用高精度，最好用上万进制以免其他地方处理不当导致TLE，
接着可以发现每一行取出来的得分和其他行没有关系，就可以分开计算，最后把所有行加起来就行了。
至于这个计算，很容易想到dp，用f[i][j]表示第i次取数，左边取了j个，或者f[i][j]表示左边取了i个，
右边取了j个，总之能表示出左右分别取了多少个就行了。
就说第一种的方程
f[i][j] = max(f[i - 1][j - 1] + a[l][j], f[i - 1][j] + a[l][m - i + j - 1]);
我做的时候稍微有点不一样，但是思路还是一样的，仍然很容易理解
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<map>
using namespace std;
typedef bool boolean;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
}
typedef class HP{
public:
int w[];
HP(){
memset(w, , sizeof(w));
}
HP(long long x){
memset(w, , sizeof(w));
if(x == ) w[] = ;
while(x > ){
w[++w[]] = x % ;
x /= ;
}
}
HP operator *(int x){
HP result;
result[] = w[] + ;
for(int i = ; i <= w[] + ; i++){
result[i] += w[i] * x;
result[i + ] += result[i] / ;
result[i] %= ;
}
while(result[result[]] == && result[] > ) result[]--;
return result;
}
HP operator +(HP another){
HP result;
result[] = max(w[], another[]) + ;
for(int i = ; i < result[]; i++){
result[i] += w[i] + another[i];
result[i + ] += result[i] / ;
result[i] %= ;
}
while(result[result[]] == && result[] > ) result[]--;
return result;
}
boolean operator <(HP another) const{
if(w[] != another[]) return w[] < another[];
for(int i = w[]; i >= ; i--){
if(w[i] != another[i]) return w[i] < another[i];
}
return false;
}
int& operator [](int pos){
return w[pos];
}
}HP;
int matrix[][];
HP result[];
HP pow_2[];
int n, m;
HP f[][][];
inline void solve(int lines){
memset(f, , sizeof(f));
f[][][] = pow_2[] * matrix[lines][];
f[][][] = pow_2[] * matrix[lines][m];
for(int i = ; i <= m; i++){
for(int j = ; j < i; j++){
HP temp = max(f[i - ][j][], f[i - ][j - ][]);
f[i][j][] = temp + pow_2[i] * matrix[lines][j + ];
f[i][j][] = temp + pow_2[i] * matrix[lines][m - i + j + ];
}
}
for(int i = ; i < m; i++){
for(int j = ; j < ; j++){
result[lines] = max(result[lines], f[m][i][j]);
}
}
}
ostream& operator <<(ostream& out, HP& x){
int buf[];
for(int i = x[]; i >= ; i--){
if(i != x[]){
memset(buf, , sizeof(buf));
int c = x[i];
while(c > ){
buf[++buf[]] = c % ;
c /= ;
}
for(int i = ; i >= ; i--)
putchar(buf[i] + '');
}else{
printf("%d",x[i]);
}
}
return out;
}
inline void init(){
readInteger(n);
readInteger(m);
for(int i = ; i <= n; i++){
for(int j = , x; j <= m; j++){
readInteger(matrix[i][j]);
}
}
pow_2[] = HP();
for(int i = ; i <= m + ; i++)
pow_2[i] = pow_2[i - ] * ;
}
HP ans;
int main(){
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
init();
ans[] = ;
for(int i = ; i <= n; i++){
solve(i);
ans = ans + result[i];
}
cout<<ans;
return ;
}
矩阵取数游戏
3.树网的核
思考一下，是不是并没有想出dp之类的十分高效的算法？再看看数据范围，n最大才300，不怕，暴力都很容易过（当然，
这是对于现在的电脑）。不过有一点还是要清楚，一定得找出一条直径来，接着在上面一段一段地去枚举。
需要枚举所有的直径吗？不需要，画画图就知道了
接着还有，怎么提高枚举的效率？首先选一段的偏心距不会多于选一个节点作为核的偏心距，而且这一道题也不要求输出
方案，所以能选多少就选多少，避免很多排列。
求直径还不清楚的话，我就再说一下，首先随便从一个点开始dfs找出一个离它最远的点，再从这个点开始dfs找出一个离它
最远的点，然后这两个点的距离就是直径的长度，注意还要记录路径
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
typedef bool boolean;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
}
typedef class Edge{
public:
int end;
int next;
int v;
Edge(const int end = , const int next = , const int v = ):end(end),next(next), v(v){}
}Edge;
int ce;
int *h;
Edge* edge;
inline void addEdge(int from, int end, int v){
edge[++ce] = Edge(end, h[from], v);
h[from] = ce;
}
int* buf;
int imn;
int maxdis;
int *rd;
int *brd;
boolean *visable;
void dfs(int* path, int node, int dis, int last, int d){
if(path != NULL){
buf[++buf[]] = node;
if(buf[] != )
brd[buf[] - ] = d;
}
if(dis > maxdis){
maxdis = dis;
if(path != NULL){
memcpy(path, buf, sizeof(int) * (buf[] + ));
memcpy(rd, brd, sizeof(int) * (buf[] + ));
}
imn = node;
}
for(int i = h[node]; i != ; i = edge[i].next){
int e = edge[i].end;
if(e == last) continue;
if(!visable[e]) continue;
dfs(path, e, dis + edge[i].v, node, edge[i].v);
}
if(path != NULL) buf[]--;
}
int n, s;
int *road;
inline void init(){
readInteger(n);
readInteger(s);
edge = new Edge[(const int)(n * )];
h = new int[(const int)(n + )];
buf = new int[(const int)(n + )];
road = new int[(const int)(n + )];
rd = new int[(const int)(n + )];
brd = new int[(const int)(n + )];
memset(h, , sizeof(int) * (n + ));
memset(buf, , sizeof(int) * (n + ));
visable = new boolean[(const int)(n + )];
memset(visable, true, sizeof(boolean) * (n + ));
for(int i = , a, b, v; i < n; i++){
readInteger(a);
readInteger(b);
readInteger(v);
addEdge(a, b, v);
addEdge(b, a, v);
}
}
inline void solve(){
dfs((int*), , , , );
maxdis = ;
dfs(road, imn, , , );
buf[] = ;
maxdis = ;
int len = ;
int l = , r = ;
int cn = ;
int result = 0xfffffff;
visable[road[]] = false;
while(r <= road[] && l <= r){
while(r < road[] && (len + rd[r] <= s)){
len += rd[r];
r++;
cn++;
visable[road[r]] = false;
}
int p = ;
for(int i = l; i <= r; i++){
maxdis = ;
dfs((int*), road[i], , , );
p = max(p, maxdis);
}
if(p < result) result = p;
visable[road[l]] = true;
cn--;
if(cn > )
len -= rd[l];
else if(r < road[]){
len = ;
r++;
visable[road[r]] = false;
}
l++;
}
cout<<result;
}
int main(){
freopen("core.in", "r", stdin);
freopen("core.out", "w", stdout);
init();
solve();
return ;
}
树网的核