ACM模板
Dijkstra 模板
/***************************************
* About: 有向图的Dijkstra算法实现
* Author: Tanky Woo
* Blog: https://www.sodocs.net/doc/757623999.html,
***************************************/
#include
using namespace std;
const int maxnum = 100;
const int maxint = 999999;
// 各数组都从下标1开始
int dist[maxnum]; // 表示当前点到源点的最短路径长度
int prev[maxnum]; // 记录当前点的前一个结点, 用于需要输出最短路径的路径是使用
int c[maxnum][maxnum]; // 记录图的两点间路径长度，用于记录当前的图
int n, line; // 图的结点数和路径数
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
bool s[maxnum]; // 判断是否已存入该点到S集合中
for(int i=1; i<=n; ++i) // 初始值为从v点到他相邻边的距离，不相邻的置为inf（maxint）{
dist[i] = c[v][i];
s[i] = 0; // 初始都未用过该点
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = 1;
// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
// 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
for(int i=2; i<=n; ++i)
{
int tmp = maxint;
int u = v; //使用u=v 是为了防止出现有多个连通分量的问题。当需要到达的点无法到达时，该点的dist[x]值必为maxint
// 找出当前未使用的点j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!s[j]) && dist[j] { u = j; // u保存当前邻接点中距离最小的点的号码 tmp = dist[j]; } s[u] = 1; // 表示u点已存入S集合中 // 更新dist for(int j=1; j<=n; ++j) if((!s[j]) && c[u][j] { //加上目前到达的点到他邻接的点的距离和其他到达该点的路径长度 int newdist = dist[u] + c[u][j]; if(newdist < dist[j]) { dist[j] = newdist; prev[j] = u; } } } } void searchPath(int *prev,int v, int u) //用于返回具体的路径 { int que[maxnum]; int tot = 1; que[tot] = u; tot++; int tmp = prev[u]; while(tmp != v) { que[tot] = tmp; tot++; tmp = prev[tmp]; } que[tot] = v; for(int i=tot; i>=1; --i) if(i != 1) cout << que[i] <<" ->"; else cout << que[i] << endl; } int main() { freopen("input.txt", "r", stdin); // 各数组都从下标1开始 // 输入结点数 cin >> n; // 输入路径数 cin >> line; int p, q, len; // 输入p, q两点及其路径长度 // 初始化c[][]为maxint for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) c[i][j] = maxint; for(int i=1; i<=line; ++i) { cin >> p >> q >> len; if(len < c[p][q]) // 有重边 { c[p][q] = len; // p指向q c[q][p] = len; // q指向p，这样表示无向图 } } for(int i=1; i<=n; ++i) dist[i] = maxint; for(int i=1; i<=n; ++i) { for(int j=1; j<=n; ++j) printf("%8d", c[i][j]); printf("\n"); } Dijkstra(n, 1, dist, prev, c); // 最短路径长度 cout <<"源点到最后一个顶点的最短路径长度: "<< dist[n] << endl; // 路径 cout <<"源点到最后一个顶点的路径为: "; searchPath(prev, 1, n); 例题： 最少换乘 时间限制：2000 ms | 内存限制：65535 KB 欧洲某城是一个著名的旅游胜地，每年都有成千上万的人前来观光旅行。Dr. Kong 决定利用暑假好好游览一番。。 年轻人旅游不怕辛苦，不怕劳累，只要费用低就行。但Dr. Kong年过半百，他希望乘坐BUS从住的宾馆到想去游览的景点，期间尽可量地少换乘车。 Dr. Kon买了一张旅游地图。他发现，市政部门为了方便游客，在各个旅游景点及宾馆，饭店等地方都设置了一些公交站并开通了一些单程线路。每条单程线路从某个公交站出发，依次途经若干个站，最终到达终点站。 但遗憾的是，从他住的宾馆所在站出发，有的景点可以直达，有的景点不能直达，则他可能要先乘某路BUS坐上几站，再下来换乘同一站的另一路BUS, 这样须经过几次换乘后才能到达要去的景点。 为了方便，假设对该城的所有公交站用1，2，……，N编号。Dr. Kong所在位置的编号为1，他将要去的景点编号为N。 请你帮助Dr. Kong寻找一个最优乘车方案,从住处到景点，中间换车的次数最少。 输入第一行： K 表示有多少组测试数据。（2≤k≤8） 接下来对每组测试数据： 第1行: M N 表示有M条单程公交线路，共有N站。（1<=M<=100 1 第2~M+1行：每行描述一路公交线路信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。 输出对于每组测试数据，输出一行，如果无法乘坐任何线路从住处到达景点，则输 出"N0"，否则输出最少换车次数，输出0表示不需换车可以直达。 样例输入 2 3 7 6 7 4 7 3 6 2 1 3 5 2 6 1 3 5 2 6 4 3 样例输出 2 NO #include #include #include using namespace std; int arr[505][505]; int temp[505]; void disj(int m,int n){ //dis用来计算最小换乘的次数，n表示公交车站点的数目m表示有多少条线路 int i, j, index=0, flag; int temp[505]; int known[505]; memset(temp, 0, sizeof(temp)); memset(known, 0, sizeof(known)); for(i=1; i<=n; ++i){ if(arr[1][i] == 1) temp[i] = arr[1][i]; else if(arr[1][i] == 0) temp[i] = 1E30; } known[1] = 1; for(i=2; i<=n; ++i){ flag = 1E30; for(j=1; j<=n; ++j){ if(!known[j] && temp[j] flag = temp[j]; index = j; } } known[index] = 1; for(j=1; j<=n; ++j){ if(!known[j] && temp[j]>temp[index]+1 && arr[index][j]) temp[j] = temp[index]+1; } } int x = 1E30; if(temp[n]!=x) printf("%d\n",temp[n]-1); else printf("NO\n"); } int main(){ int t; cin>>t; while(t--){ int i, j, k, l; char ss[2000]; int m, n; cin>>m>>n; getchar(); memset(arr,0,sizeof(arr)); for(i=1; i<=m;++i){ gets(ss); int len = strlen(ss); l=0; for(j=0; j int sum=0; for(k=j; ss[k]!=' '&& ss[k]!='\0';){ sum = sum*10 + ss[k]-'0'; k++; j++; } j+=1; temp[++l]=sum; } for(j=1; j<=l; ++j){ for(k=j+1; k<=l; ++k){ arr[temp[j]][temp[k]] = 1; } } } /* cout< for(i=1; i<=n;++i){ for(j=1; j<=n; ++j){ printf("%d ",arr[i][j]); } cout< } */ disj(m, n); } return 0; } A strange lift Problem Description There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up a nd down.When you at floor i,if you press the button "UP" , you will go up Ki floor, i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can' t go up high than N,and can't go down lower than 1. For example, there is a buli ding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you'll go up to the 4 th floor,and if you press the button "DOWN", the lift can't do it, because it can't go down to the -2 th floor,as you know ,the -2 th floor isn't exist. Here comes the problem: when you are on floor A,and you want to go to floor B, how many times at least he has to press the button "UP" or "DOWN"? Input The input consists of several test cases.,Each test case contains two lines. The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,....kn. A single 0 indicate the end of the input. Output For each case of the input output a interger, the least times you have to press th e button when you on floor A,and you want to go to floor B.If you can't reach flo or B,printf "-1". Sample Input 5 1 5 3 3 1 2 5 Sample Output 3 Recommend 8600 #include using namespace std; #define INF 999999 int map[500][500]; int dist[500],used[500]; int n; void Dijkstra(int v) { int i,j,pos,min; memset(used,0,sizeof(used)); for(i=1;i<=n;i++) dist[i]=map[v][i]; used[v]=1; dist[v]=0;//floor A==floor B(起点就是终点)的情况 for(j=1;j { pos=0; min=100000000; for(i=1;i<=n;i++) if(dist[i] { pos=i; min=dist[i]; } used[pos]=1; for(i=1;i<=n;i++) if(dist[i]>dist[pos]+map[pos][i]) dist[i]=dist[pos]+map[pos][i]; } } int main() { int s,t,i,j; int a[500]; while(cin>>n,n) { cin>>s>>t; memset(map,INF,sizeof(map)); for(i=1;i<=n;i++) { cin>>a[i]; if(i+a[i]<=n) map[i][i+a[i]]=1;//构图必须是单向边 if(i-a[i]>=1) map[i][i-a[i]]=1; } Dijkstra(s); if(dist[t]>INF)//If you can't reach floor B,printf "-1" cout<<-1< else cout< } return 0; } 昂贵的聘礼 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要 5000金币就行了。"探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。 为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。 Input 输入第一行是两个整数M，N（1 <= N <= 100），依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和"优惠价格"。 Output 输出最少需要的金币数。 Sample Input 1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0 Sample Output 5250 #include using namespace std; const int INF=100000; int a[105][105],b[105],c[105],s[105],dist[105]; int n,m; int dj(int p,int q) { int i,j,r,t,k=0; for(i=0;i if((b[i]>=p&&b[i]<=q)) dist[i]=a[k][i], s[i]=0; else dist[i]=INF,s[i]=0; dist[0]=0; s[0]=1; for(i=1;i { t=INF; for(j=0;j if(!s[j]&&dist[j] s[k]=1; for(j=0;j if(!s[j]&&a[k][j] { r=dist[k]+a[k][j]; if(dist[j]>r) dist[j]=r; } } t=c[0]; for(i=0;i if(dist[i]+c[i] return t; } int main(int argc, char *argv[]) { int i,j,k,p,q,l,r; while(cin>>m>>n&&(m||n)) { for(i=0;i for(j=0;j a[i][j]=INF; for(i=0;i { cin>>c[i]>>b[i]>>k; for(j=0;j { cin>>p>>q; a[i][p-1]=q; } } r=c[0]; for(i=b[0]-m;i<=b[0];i++) { k=dj(i,i+m); if(k } cout< } return 0; } prim算法模板 + 思路 /* Prim:利用dis[]来记录已选点集中到各点的最短距离，一开始用起始点到各点的距离初始化dis[] while->知道全部点都走到 for->找dis[]中最小边（保证不出现环，即不出现最小边所关联的两个定点都在已选点集中），添加长度，添加点进已选点集 for->利用刚添加进来的点到各点的距离，更新dis[] */ #include #include #define MaxInt 0x3f3f3f3f #define N 110 //创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问 int map[N][N],low[N],visited[N]; //low的含义就是visited【i】为0的情况下 int n; //选中点集的各个点到未选中点集的各个点的最短距离 int prim() { int i,j,pos,min,result=0; memset(visited,0,sizeof(visited)); //从某点开始，分别标记和记录该点 visited[1]=1;pos=1; //第一次给low数组赋值, for(i=1;i<=n;i++) { if(i!=pos) low[i]=map[pos][i]; } //再运行n-1次 for(i=1;i { //找出最小权值并记录位置 min=MaxInt; for(j=1;j<=n;j++) { if(visited[j]==0&&min>low[j]) { min=low[j];pos=j; } } //最小权值累加 result+=min; //标记该点 visited[pos]=1; //更新权值 for(j=1;j<=n;j++) { if(visited[j]==0&&low[j]>map[pos][j]) { low[j]=map[pos][j]; } } } return result; } int main() { int i,v,j,ans; while(scanf("%d",&n)!=EOF) { //所有权值初始化为最大 memset(map,MaxInt,sizeof(map)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&v); map[i][j]=map[i][j]=v; } ans=prim(); printf("%d\n",ans); } return 0; } 畅通工程 #include #include #include #define INF 999999999 using namespace std; int map[105][105],visit[105],dis[105],M; int prim() { int i,j; for(i = 1;i <= M; i++) { dis[i] = map[i][1]; } dis[1] = 0; int sum = 0; for(i = 1; i <= M; i++) { int temp = INF,pos; for(j= 1; j <= M; j++) { if(!visit[j] && temp > dis[j]) { temp = dis[j]; pos = j; } } if(temp == INF) return 0; visit[pos] = 1; sum += dis[pos]; for(j = 1; j <= M; j++) { if(!visit[j] && map[pos][j] < dis[j] && map[pos][j]!=INF) { dis[j] = map[pos][j]; } } } return sum; } int main() { int N; while(scanf("%d%d",&N,&M),N) { int u,v,w; memset(map,0x3f,sizeof(map)); memset(dis,0x3f,sizeof(dis)); memset(visit,0,sizeof(visit)); for(int i = 1; i <= N; ++i) { scanf("%d%d%d",&u,&v,&w); map[u][v] = map[v][u] = w; } int ans = prim(); if(ans) printf("%d\n",ans); else printf("?\n"); } return 0; } Freckles 雀斑 In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle. 输入： The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle. 输出： Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles. 样例输入： 3 1.0 1.0 2.0 2.0 2.0 4.0 样例输出： 3.41 #include #include #include #define max 1<<30 struct node { double x,y; }e[105]; int vis[105],n; double map[105][105],sum,p[105]; void prim() { int i,j,k; double min; sum=0.0; for(i=1;i p[i]=map[0][i]; vis[0]=1; for(i=1;i { min=max; for(j=1;j { if(!vis[j]&&p[j] { min=p[j]; k=j; } } sum+=min; vis[k]=1; for(j=1;j { if(!vis[j]&&map[k][j] p[j]=map[k][j]; } } } int main() { int i,j; while(~scanf("%d",&n)) { memset(vis,0,sizeof(vis)); for(i=0;i scanf("%lf%lf",&e[i].x,&e[i].y); for(i=0;i { for(j=0;j map[i][j]=map[j][i]=sqrt((e[i].x-e[j].x)*(e[i].x-e[j].x)+(e[i].y-e[j].y)*(e[i].y-e[j].y)); } prim(); printf("%.2lf\n",sum); } return 0; } 并查集 普通并查集： 带路径压缩的的findset函数：1.while版本 2.递归版本 个人经验表明在递归版本不栈溢出的情况下，递归版本和循环版本的效率并没有太大差别，并且对于带路径压缩的并查集，基本上不会发生“递归栈溢出”。 另外，union_nodes函数还可以可以采用启发式合并，思路就是把深度较小的那棵子树并到深度较大的那棵子树上，不过一般情况下路径压缩就够用了。 听人说并查集还可以“离散化”，个人从字面上理解应该是指用map、hash来保存每个节点，从而当节点分布比较稀疏的时候，可以比普通并查集更快的完成初始化等工作（待商榷）。 代码： 小希的迷宫 上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon 来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。 Input 输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。 整个文件以两个-1结尾。 Output 对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出"Yes"，否则输出"No"。 Sample Input 6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1 Sample Output Yes Yes No 电子科技大学 期末解题报告 课程：《ACM算法与程序设计》学院： 学号： 姓名： 报告成绩：教师签名： 讨厌的青蛙 1、链接地址 https://www.sodocs.net/doc/757623999.html,/problem?id=2812 2、问题描述 在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同，如图1所示。稻田里的稻子组成一个栅格，每棵稻子位于一个格点上，如图2所示。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去，如图3所示。 问题描述 青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。可能会有多只青蛙从稻田穿越，有些水稻被多只青蛙踩踏，如图4所示。当然，农民所见到的是图5中的情形，看不到图4中的直线。 根据图5，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3 棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3 棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径。在图5中，格点(2, 1)、(6, 1)上的水稻可能是同一只青蛙踩踏的，但这条线上只有两棵被踩踏的水稻，因此不能作为一条青蛙行走路径；格点(2, 3)、(3, 4)、(6, 6)在同一条直线上，但它们的间距不等，因此不能作为一条青蛙行走路径；格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路径，该路径不包括格点(2, 6)。请你写一个程序，确定在所有的青蛙行路径中，踩踏水稻棵数最多的路径上有多少棵水稻被踩踏。例如，图5的答案是7，因为第6 行上全部水稻恰好构成一条青蛙行走路径。 题目来源：福州大学acm网站 代码：fpcdq 一、入门 熟悉ACM竞赛规则以及程序提交注意事项 例题： Problem 1000 A+B Problem Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description Calculate a + b. Input The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line. Output For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input. Sample Input 1 5 2 3 Sample Output 6 5 My answer： #include acm论文模板范文 ACM是全世界领域影响力最大的专业学术组织。而acm模板，你 们知道吗?这是 ___为大家了两篇acm论文，这样你们对模板会有直观的印象! [摘要] 鉴于ACM大学生程序设计竞赛(ACM/ICPC)在人才选拔和培养方面的显著作用，如何将ACM/ICPC竞赛活动嵌入常规教学，创新教学模式，结合专业教学，加强训练管理，提高培训效益，已成为人们关注的问题。针对这一应用需求，本文设计并开发了基于ACM/ICPC机制的大学生程序设计培训管理系统。系统采用B/S架构，以SQL Server xx作为后台管理数据库，Visual Studio 和https://www.sodocs.net/doc/757623999.html,为前端开发工具。在分析系统功能的基础上，着重阐述了 该系统设计与实现的关键技术。该系统实际运行稳定、可靠，为开展ACM/ICPC竞赛培训和教学提供了一种有效管理途径。 [关键词] ACM/ICPC;培训管理系统;Web开发;https://www.sodocs.net/doc/757623999.html,;数据库技 术 doi ： 10 . 3969 / j . issn . 1673 - 0194 . xx . 03. 015 [] TP311 [] A [] 1673 - 0194(xx)03- 0028- 03 1 引言 ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest， ACM ICPC) 由美国计算机协会(ACM)主办，始于1970年，至今已经有40多年的，是世界公认的规模最大、水平最高、影响广泛的国际大学生程序设计竞赛，竞赛优胜者是各大IT企业和科研院所青睐和优先选拔的人才[1]。近些年来，伴随着ACM/ICPC大学生程序设计竞赛在国内如火如荼地开展，计算机界更加关注在人才培养方面，如何科学合理地引入、借鉴ACM/ICPC竞赛训练，将ACM/ICPC竞赛活动与常规专业课程教学有机结合起来，突破传统教学内容和，以有效培养学生的学习能力、创新意识和综合素质。这其中，如何有效组织开展ACM/ICPC竞赛训练，加强培训管理，提高培训效益，亦是人们关注的热点问题。 但就目前情况来看，组织开展此项竞赛活动的训练指导或教学培训还没有一个成熟通用的、基于ACM/ICPC竞赛机制的ACM/ICPC 训练和活动的教学管理平台。具体表现在：(1)尽管一些知名院校搭建了自己的在线测试平台[2-3]，但由于大多采用英文表述问题，对于水平不高的低年级本科生和专科学生来说，在翻译题目和理解内容方面会出现偏差，导致在这些平台上进行在线模拟测验的效果并不理想;(2)很多网站虽然提供了ACM/ICPC竞赛的相关资料，比如网上题库、相关赛题的题解等，但这些资料在网上分布得比较分散，使 ACM模板 [ 王克纯 2020年9月21日 最大子串 int maxSum(int * a,int n) { int sum = a[0],b = 0; for(int i=0;i 1、0-1背包 #include } } m[0][c]=m[1][c]; if(c>=w[0]) { if(m[0][c] 1111111杭电： 1000 A + B Problem (4) 1001 Sum Problem (5) 1002 A + B Problem II (6) 1005 Number Sequence (8) 1008 Elevator (9) 1009 FatMouse' Trade (11) 1021 Fibonacci Again (13) 1089 A+B for Input-Output Practice (I) (14) 1090 A+B for Input-Output Practice (II) (15) 1091 A+B for Input-Output Practice (III) (16) 1092 A+B for Input-Output Practice (IV) (17) 1093 A+B for Input-Output Practice (V) (18) 1094 A+B for Input-Output Practice (VI) (20) 1095 A+B for Input-Output Practice (VII) (21) 1096 A+B for Input-Output Practice (VIII) (22) 1176 免费馅饼 (23) 1204 糖果大战 (25) 1213 How Many Tables (26) 2000 ASCII码排序 (32) 2001 计算两点间的距离 (34) 2002 计算球体积 (35) 2003 求绝对值 (36) 2004 成绩转换 (37) 2005 第几天？ (38) 2006 求奇数的乘积 (40) 2007 平方和与立方和 (41) 2008 数值统计 (42) 2009 求数列的和 (43) 2010 水仙花数 (44) 2011 多项式求和 (46) 2012 素数判定 (47) 2014 青年歌手大奖赛_评委会打分 (49) 2015 偶数求和 (50) 2016 数据的交换输出 (52) 2017 字符串统计 (54) 2019 数列有序! (55) 2020 绝对值排序 (56) 2021 发工资咯：） (58) 2033 人见人爱A+B (59) 2037 今年暑假不AC (61) 2039 三角形 (63) 2040 亲和数 (64) 1、KMP 算法 /* * next[]的含义：x[i-next[i]...i-1]=x[0...next[i]-1] * next[i]为满足x[i-z...i-1]=x[0...z-1]的最大z值（就是x的自身匹配） */ void kmp_pre(char x[],int m,int next[]) { int i,j; j=next[0]=-1; i=0; while(i ACM Word Template for SIG Site 1st Author 1st author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 1st author's E-mail address 2nd Author 2nd author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 2nd E-mail 3rd Author 3rd author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 3rd E-mail ABSTRACT A s network speed continues to grow, new challenges of network processing is emerging. In this paper we first studied the progress of network processing from a hardware perspective and showed that I/O and memory systems become the main bottlenecks of performance promotion. Basing on the analysis, we get the conclusion that conventional solutions for reducing I/O and memory accessing latencies are insufficient for addressing the problems. Motivated by the studies, we proposed an improved DCA combined with INIC solution which has creations in optimized architectures, innovative I/O data transferring schemes and improved cache policies. Experimental results show that our solution reduces 52.3% and 14.3% cycles on average for receiving and transmitting respectively. Also I/O and memory traffics are significantly decreased. Moreover, an investigation to the behaviors of I/O and cache systems for network processing is performed. And some conclusions about the DCA method are also presented. Keywords Keywords are your own designated keywords. 1.INTRODUCTION Recently, many researchers found that I/O system becomes the bottleneck of network performance promotion in modern computer systems [1][2][3]. Aim to support computing intensive applications, conventional I/O system has obvious disadvantages for fast network processing in which bulk data transfer is performed. The lack of locality support and high latency are the two main problems for conventional I/O system, which have been wildly discussed before [2][4]. To overcome the limitations, an effective solution called Direct Cache Access (DCA) is suggested by INTEL [1]. It delivers network packages from Network Interface Card (NIC) into cache instead of memory, to reduce the data accessing latency. Although the solution is promising, it is proved that DCA is insufficient to reduce the accessing latency and memory traffic due to many limitations [3][5]. Another effective solution to solve the problem is Integrated Network Interface Card (INIC), which is used in many academic and industrial processor designs [6][7]. INIC is introduced to reduce the heavy burden for I/O registers access in Network Drivers and interruption handling. But recent report [8] shows that the benefit of INIC is insignificant for the state of the art 10GbE network system. In this paper, we focus on the high efficient I/O system design for network processing in general-purpose-processor (GPP). Basing on the analysis of existing methods, we proposed an improved DCA combined with INIC solution to reduce the I/O related data transfer latency. The key contributions of this paper are as follows: ?Review the network processing progress from a hardware perspective and point out that I/O and related last level memory systems have became the obstacle for performance promotion. ?Propose an improved DCA combined with INIC solution for I/O subsystem design to address the inefficient problem of a conventional I/O system. ?Give a framework of the improved I/O system architecture and evaluate the proposed solution with micro-benchmarks. ?Investigate I/O and Cache behaviors in the network processing progress basing on the proposed I/O system. The paper is organized as follows. In Section 2, we present the background and motivation. In Section 3, we describe the improved DCA combined INIC solution and give a framework of the proposed I/O system implementation. In Section 4, firstly we give the experiment environment and methods, and then analyze the experiment results. In Section 5, we show some related works. Finally, in Section 6, we carefully discuss our solutions with many existing technologies, and then draw some conclusions. 2.Background and Motivation In this section, firstly we revise the progress of network processing and the main network performance improvement bottlenecks nowadays. Then from the perspective of computer architecture, a deep analysis of network system is given. Also the motivation of this paper is presented. 2.1Network processing review Figure 1 illustrates the progress of network processing. Packages from physical line are sampled by Network Interface Card (NIC). NIC performs the address filtering and stream control operations, then send the frames to the socket buffer and notifies #include 目录 1.最小生成树 (2) 2.最短路算法 (7) 3.素数打表 (11) 4.最大匹配 (12) 5.线段树（敌兵布阵） (14) 6．线段树（逆序树） (16) 7.树形dp (18) 8.树状数组（段跟新） (20) 9.Kmp模板 (22) 10.线段树（点跟新） (26) 11.强连通 (28) 12.最小割 (31) 13.单源最短路（spfa） (34) 14.三分查找 (36) 15.字典树（统计难题） (38) 16.最大流入门题1273 (40) 17.状态压缩 (43) 18.匈牙利（HDU 2063）（最大匹配） (45) 19.凸包（HDU1348） (47) 20.树状数组(HDU1166) (50) 21.强连通 (52) 22.前向星 (55) 23.矩阵 (58) 24.并查集 (60) 25. SORT (61) 26. STL (63) 27. LCA (HDU 2874) (67) 28. 01背包 (70) 29. 状态压缩代码： (72) 30. 快速幂 (74) 31.矩阵快速幂 (75) 32.GCD & LCM (77) 33.ACM小技巧： (78) 34. /** 大数（高精度）求幂**/ (80) 35. /** 大数除法与求余**/ (82) 36. /** 大数阶乘**/ (84) 37. /** 大数乘法**/ (85) 38. /** 大数累加**/ (86) 1.最小生成树 要连通n个城市需要n－1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。 prim算法（矩阵形式）： #define inf 0x3f3f3f3f int prim(int n,int sta)//n表示有n个顶点，sta表从sta这个顶点出发生成最小生成树{ int mark[M],dis[M]; int i,sum = 0; //sum是总的最小生成树边权值 for (i = 0;i < n;i ++) //初始化dis[i] 表从顶点sta到点i的权值 { dis[i] = mat[sta][i]; mark[i] = 0; } mark[sta] = 1; //sta 这个顶点加入最小生成树中 for (i = 1;i < n;i ++) //循环n-1次，每次找出一条最小权值的边 n个点的图 { //只有n-1条边 int min = inf; //inf 表无穷大 for (j = 0;j < n;j ++)//找出当前未在最小生成树中边权最小的顶点 if (!mark[j] && dis[j] < min) min = dis[j],flag = j; mark[flag] = 1; //把该顶点加入最小生成树中 sum += dis[flag]; //sum加上其边权值 for (j = 0;j < n;j ++) //以falg为起点更新到各点是最小权值 if (dis[j] > mat[flag][j]) dis[j] = mat[flag][j]; } return sum; //返回边权总和 } prim算法（边表形式）： struct Edge//frm为起点,to为终点，w为边权，nxt指向下一个顶点 { // int frm; int to,w,nxt; }edge[M]; int vis[M],head[M],dis[M]; void addedge (int cu,int cv,int cw)//生成边的函数 ACM Word Template for SIGCOMM Submissions 1st Author 1st author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 1st author's email address 2nd Author 2nd author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 2nd E-mail 3rd Author 3rd author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 3rd E-mail ABSTRACT In this paper, we describe the formatting guidelines for ACM SIG Proceedings. Categories and Subject Descriptors D.3.3 [Programming Languages]: Language Contructs and Features –abstract data types, polymorphism, control structures. This is just an example, please use the correct category and subject descriptors for your submission.The ACM Computing Classification Scheme: https://www.sodocs.net/doc/757623999.html,/class/1998/ General Terms Your general terms must be any of the following 16 designated terms: Algorithms, Management, Measurement, Documentation, Performance, Design, Economics, Reliability, Experimentation, Security, Human Factors, Standardization, Languages, Theory, Legal Aspects, Verification. Keywords Keywords are your own designated keywords. 1.INTRODUCTION The proceedings are the records of the conference. ACM hopes to give these conference by-products a single, high-quality appearance. To do this, we ask that authors follow some simple guidelines. In essence, we ask you to make your paper look exactly like this document. The easiest way to do this is simply to down-load a template from [2], and replace the content with your own material. 2.PAGE SIZE All material on each page should fit within a rectangle of 18 x 23.5 cm (7" x 9.25"), centered on the page, beginning 1.9 cm (0.75") from the top of the page and ending with 2.54 cm (1") from the bottom. The right and left margins should be 1.9 cm (.75”). The text should be in two 8.45 cm (3.33") columns with a .83 cm (.33") gutter. 3.TYPESET TEXT 3.1Normal or Body Text Please use a 10-point Times Roman font, or other Roman font with serifs, as close as possible in appearance to Times Roman in which these guidelines have been set. The goal is to have a 10-point text on 12-point leading, as you see here. Please use sans-serif or non-proportional fonts only for special purposes, such as distinguishing source code text. If Times Roman is not available, try the font named Computer Modern Roman. On a Macintosh, use the font named Times. Right margins should be justified, not ragged. 3.2Title and Authors The title (Helvetica 18-point bold), authors' names (Helvetica 12-point) and affiliations (Helvetica 10-point) run across the full width of the page –one column wide. We also recommend phone number (Helvetica 10-point) and e-mail address (Helvetica 12-point). See the top of this page for three addresses. If only one address is needed, center all address text. For two addresses, use two centered tabs, and so on. For more than three authors, you may have to improvise.1 3.3First Page Copyright Notice Please leave 3.81 cm (1.5") of blank text box at the bottom of the left column of the first page for the copyright notice. 3.4Subsequent Pages For pages other than the first page, start at the top of the page, and continue in double-column format. The two columns on the last page should be as close to equal length as possible. 1If necessary, you may place some address information in a footnote, or in a named section at the end of your paper. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Conference’04, Month 1–2, 2004, City, State, Country. Copyright 2004 ACM 1-58113-000-0/00/0004…$5.00.《ACM算法与程序设计》解题报告模板
ACM题目整理
acm论文模板范文
我的ACM算法模板
ACM动态规划问题简易模板(C++可编译)
整理出ACM所有题目及答案
整理acm模板
ACM的论文写作格式标准
acm-计算几何模板
ACM比赛模板
ACM Word Template for SIGCOMM Submissions