比赛链接：click here~~
密码：nyist
Description
作为计算机系的学生，算法与数据结构是必修的主干课程，因此课程的每个老师都很关心每个学生的学习情况，每天下课老师都会给某个学生进行课外辅导。首先，老师会给每个学生一个能力评定分数，如果有学生要求老师给他辅导，那老师就会专门给该同学进行课外辅导，如果没有学生要求，老师就会给评定分数最低的同学课外辅导。老师给学生辅导后，学生的能力都会有所增长，然而不同的学生增长的情况都不同。老师想知道为学生课外辅导若干天后，全班的最低分学生的编号和分数。
Input
第一行有一个数字n，表示有n个学生，编号从1到n。(1 <= n <= 10000)。
接下来一行有n个数，分别是编号从1到n的学生的初始能力水平xi，(1 <= xi <= 1000)。
接下来有一行有一个数m表示老师给学生课外辅导了m天(1 <= m <= 100000)。
接下来m行，每行两个数(ai bi)，表示老师在第i天给编号为ai同学补课，编号为ai的同学能力提高了bi(0 <= ai <= n,1 <= bi <= 1000)。如果ai为0，则表示老师今天给能力最差的学生辅导。如果最低分同时有多个学生，就给编号小的学生补课。
Output
Sample Input
Sample Output
Hint
第一天后：110 20 30
第二天后：110 20 40
第三天后：110 60 40
一看就知道是线段树，但是线段树还没学啊~~最后发现可以用到优先队列解决：
代码：
#include <stdio.h> //优先队列模拟
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
struct nod
{
int val,num;
friend bool operator < (nod a,nod b)
{
if(a.val!=b.val)
return a.val>b.val;
else return a.num>b.num;
}
} a[10050],b;
int main()
{
int t,n,m,i,tot=1;
scanf("%d",&t);
while(t--)
{
priority_queue <nod>Q; // 一定要加在这里，放在外面会WA
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d",&a[i].val);
a[i].num=i;
Q.push(a[i]);
}
scanf("%d",&m);
while(m--)
{
int k,q;
scanf("%d%d",&k,&q);
if(!k) //编号为0 的时候
{
while(1)
{
b=Q.top(); // 取栈顶
Q.pop();
if(a[b.num].val==b.val) // 判断
{
a[b.num].val+=q;
Q.push(a[b.num]);// 压栈
break;
}
else
{
Q.push(a[b.num]);//压栈
}
}
}
else
{
a[k].val+=q;
}
}
b=Q.top();
Q.pop();
while(b.val!=a[b.num].val) //最后判断一次
{
Q.push(a[b.num]);
b=Q.top();
Q.pop();
}
printf("Case %d: %d %d\n",tot++,b.num,b.val);
}
return 0;
}
最基本的线段树,每个结点记录当前线段的最小值的编号id....所以根结点的min_id域记录了
当前最低分数学生的编号..
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=1e5;
int val[maxn<<2],num[maxn<<2];
#define mem(a) memset(a,0,sizeof(a))
void Pushup(int rt)
{
if(val[rt<<1]<=val[rt<<1|1]){
val[rt]=val[rt<<1];
num[rt]=num[rt<<1];
}
else {
val[rt]=val[rt<<1|1];
num[rt]=num[rt<<1|1];
}
}
void Build(int l,int r,int rt)
{
if(l==r){
scanf("%d",&val[rt]);
num[rt]=l;
return ;
}
int m=(l+r)>>1;
Build(lson);
Build(rson);
Pushup(rt);
}
void Update(int p,int c,int l,int r,int rt)
{
if(l==r){
val[rt]+=c;
return ;
}
int m=(l+r)>>1;
if(p<=m) Update(p,c,lson);
else Update(p,c,rson);
Pushup(rt);
}
int main()
{
int T,n,m,p,c,tot=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
Build(1,n,1);
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&p,&c);
if(p==0) p=num[1];
Update(p,c,1,n,1);
}
printf("Case %d: %d %d\n",tot++,num[1],val[1]);
}
}
Description
福大新校区的周围有若干个养鸭场，当然鸭群里面也有另类的。养鸭场的老板认为，这些另类的鸭子，要么可以卖个好价钱，要么一文不值。
我们定义每只鸭子的特征为一个一维的0-1向量如：
鸭子a1在这三只鸭子里的另类度为：dist (a1,a1)+dist (a1,a2)+dist (a1,a3)。
定义dist运算为：
dist (a1,a1)= (|1-1|+|0-0|+|0-0|+|1-1|+|0-0|) = 0
dist (a1,a2) = (|1-0|+|0-1|+|0-0|+|1-0|+|0-1|) = 4;
dist (a1,a3) = (|1-0|+|0-0|+|0-1|+|1-0|+|0-1|) = 4;
就得到鸭子a1在这三只鸭子里的另类度为8。
另类的鸭子越多，风险就越大，因此，养鸭场的老板希望可以确定他的鸭群里面到底有多少另类的鸭子。
Input
每组数据第一行为空格隔开的三个整数n、m和p。n表示有n只鸭子(2 <= n <= 10,000)，m表示这群鸭子有m个特征值(5 <= m <= 200)，p表示另类度的界限，认为大于等于p的另类度的鸭子就为另类的鸭子(0 <= p <= 2,000,000)。
接下来n行，每行有m个用空格隔开的0或1数字，表示鸭子的特征值。
Output
Sample Input
Sample Output
处理好0.和1 。
代码：
//模拟
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=1e5;
//int val[maxn<<2],num[maxn<<2];
#define mem(a) memset(a,0,sizeof(a))
const int N = 10000 + 10;
const int M = 200 + 10;
int num[N][M], sum[M];
int main()
{
int T, n, m, p,tot=1;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &m, &p);
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
scanf("%d", &num[i][j]);
if(num[i][j])
sum[j]++;
}
}
int count = 0;
for(int i = 1; i <= n; i++)
{
int ans = 0;
for(int j = 1; j <= m; j++)
if(num[i][j])
ans += n-sum[j];
else
ans += sum[j];
if(ans >= p)
count++;
}
printf("Case %d: %d\n",tot++, count);
}
return 0;
}
Description
进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了死锁。
例如，如果线程A占用了资源1并等待资源2，而线程B占用了资源2并等待资源1，这样两个线程就发生了死锁现象。
为了描述系统资源分配的问题，我们用一张有向图G 来表示资源分配图。V为有向图的顶点集，包括进程结点集合P={p 1,p 2,…,p n}和资源结点集合R={r 1,r 2,…,r m}两种；E为有向边的集合，其元素包括二元组(p i,r j)或(r j,p i)。(p i,r j)表示进程p i申请资源r j，(r j,p i)表示资源r j被进程p i占用。
根据操作系统中的知识可以知道，如果在一个资源分配图中，从任意一个结点出发，都不存在一条路径能回到自身，则系统中没有死锁，否则系统中可能存在死锁。
你的任务是对于给你的一张资源分配图，判断是否可能存在死锁。
Input
每组数据的第一行是四个整数P,R,E1,E2,其中P表示进程结点数，R表示资源结点数，E1表示(pi,rj)边数，E2表示(rj,pi)边数，1 <= P,R <= 500。接下来E1行每行两个整数pi,rj,表示从结点pi到rj有一条边。接下来E2行每行两个整数rj,pi，表示从结点rj到pi有一条边。0 <= pi < P, 0 <= rj <R。
Output
Sample Input
Sample Output
并查集的运用：
代码：
//D - 死锁
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
int father[1010];
int Find(int x)
{
if(father[x]==x) return x;
else return Find(father[x]);
}
int scan()
{
int res = 0, flag = 0;
char ch;
if((ch = getchar()) == '-') flag = 1;
else if(ch >= '0' && ch <= '9') res = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9')
res = res * 10 + (ch - '0');
return flag ? -res : res;
}
int main()
{
int t,n,m,p,r,e1,e2,x,y,i,tot=1;
t=scan();
while(t--)
{
bool flag=0;
p=scan();
r=scan();
e1=scan();
e2=scan();
for(i=0;i<p+r;i++)
father[i]=i;
for(i=0;i<e1;i++)
{
x=scan();
y=scan();
father[x]=p+y;
}
for(i=0;i<e2;i++)
{
x=scan();
y=scan();
int a=Find(father[x+p]);
int b=Find(father[y]);
if(a==b) flag=1;
else father[b]=a;
}
printf("Case %d: ",tot++);
if(flag) printf("Possible\n");
else printf("Impossible\n");
}
return 0;
}Description
Input
首先给定一篇文章，以“@”结束。文章单词个数不超过1000个。
接下来一个n（1 <= n <= 1000），表示有n个询问句子。
接下来n行给定n个不完整的句子。每个句子单词个数小于等于100并带有"_"，以“@”结束。"_"表示未知的单词。
文章及给定的句子都为英文单词，并且都由小写字符组成，没有标点符号。
Output
对于每组数据的每个询问句子，回答“YES”和“NO”。
YES表示可以根据文章的内容填写该句子。
NO表示不能根据文章的内容填写该句子。
Sample Input
Sample Output
kmp算法：
代码：
Problem 1926 填空
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
int a[200001],b[200001],dp[300];
int aa[10011][300];
int father[1005];
int n,m,t,bb,i,j;
using namespace std;
const int maxn = 1005;
char str[maxn];
string s[maxn],s2[maxn];
int next[maxn];
int lens,lens2;
struct node
{
int x,y,sum;
} p[10000];
int Find(int x)
{
if(x!=father[x])
return father[x]=Find(father[x]);
return x;
}
void init(string s2[]) //构造next 数组
{
int i=0,j=-1;
next[0]=-1;
while(i<lens2){
if(j==-1||s2[i]==s2[j]||s2[i]=="_"||s2[j]=="_")
next[++i]=++j;
else
j=next[j];
}
}
int kmp(string s[],string s2[]) //KMP
{
int i=0,j= 0;
init(s2);
while(i<lens){
while(i<lens&&j<lens2){
if(j==-1||s[i]==s2[j]||s2[j]== "_"){
i++;
j++;
}
else
j=next[j];
}
if(j==lens2) return true;
}
return false;
}
int main()
{
int t,m,cas=1;
scanf("%d",&t);
while(t--)
{
int ss=0;
while(scanf("%s",str)){
if(strcmp(str,"@")==0) break;
s[ss++]=string(str);
}
printf("Case %d:\n",cas++);
lens=ss;
scanf("%d",&m);
while(m--)
{
ss=0;
while(scanf("%s",str)){
if(strcmp(str,"@")==0) break;
s2[ss++]=string(str);
}
lens2=ss;
//printf("Case %d:\n",cas++);
if(kmp(s,s2)) printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
Description
For example, if there are four integers 2,5,6,3, we could find out an equation 2+6=3+5 that satisfies A+B=C+D. If there are four integers 1,2,4,9, we could not find out any equation that satisfies A+B=C+D.
If we could use these four integers to form an equation that satisfies A+B=C+D, please output “Yes”, otherwise output “No” instead.
Input
Output
Sample Input
Sample Output
模拟：
I - An Equation:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
int a[4];
int main()
{
int t,tot=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3]);
sort(a,a+4);
if(a[0]+a[3]==a[1]+a[2])
printf("Case %d: Yes\n",tot++);
else
printf("Case %d: No\n",tot++);
}
return 0;
}
原文：http://blog.csdn.net/u013050857/article/details/44539181