#个人赛第六场解题总结#
比赛链接：click here~~
密码：nyist
A - 栀子花开
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
FZU 1921
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
对于每组数据输出一行先输出组数(从1开始)，接着最后输出经过m天后，全班的最低分学生的编号和分数。
Sample Input
1310 20 3030 1003 100 40
Sample Output
Case 1: 3 40
Hint
第一天后：110 20 30
第二天后：110 20 40
第三天后：110 60 40
【解题思路】：
一看就知道是线段树，但是线段树还没学啊~~最后发现可以用到优先队列解决：
代码：
#include //优先队列模拟#include #include #include #include #include #include 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 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 #include #include #include #include #include #include using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const 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]); }}
B - 非主流
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
FZU 1922
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
对于每组数据输出一行先输出组数(从1开始)，接着输出该群鸭子中另类的鸭子数。
Sample Input
13 5 81 0 0 1 00 1 0 0 10 0 1 0 1
Sample Output
Case 1: 1
【解题思路】：
处理好0.和1 。
代码：
//模拟#include #include #include #include #include #include #include using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const 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;}
D - 死锁
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
FZU 1924
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 Output
对于每组数据输出一行先输出组数(从1开始)，接着如果可能存在死锁输出”Possible”；如果不可能存在死锁输出一行“Impossible”。
Sample Input
22 2 1 10 10 13 3 3 40 01 12 20 12 02 11 2
Sample Output
Case 1: ImpossibleCase 2: Possible
【解题思路】：
并查集的运用：
代码：
//D - 死锁#include #include #include #include #include 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;iF - 填空
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
FZU 1926
Description
“关关雎鸠，在河之洲。窈窕淑女，君子好逑。”高中的文言文课文很多都是要求背诵的，语文老师会定期要求学生填写文章。老师会先教学生一篇课文，然后给一些句子，挖掉一些空格，要求学生把空格填补完整。因此老师需要选定文章和给定不完整的句子，并要预先做好一份答案，但是老师也有出错的时候，有些句子不能根据文章填空。对此要判断给定的句子能否根据课文填写相关的位置。
Input
首先给定一篇文章，以“@”结束。文章单词个数不超过1000个。
接下来一个n（1 <= n <= 1000），表示有n个询问句子。
接下来n行给定n个不完整的句子。每个句子单词个数小于等于100并带有"_"，以“@”结束。"_"表示未知的单词。
文章及给定的句子都为英文单词，并且都由小写字符组成，没有标点符号。
Output
对于每组数据的每个询问句子，回答“YES”和“NO”。
YES表示可以根据文章的内容填写该句子。
NO表示不能根据文章的内容填写该句子。
Sample Input
1much of the language used to describe monetary policy such as steering the economy to a soft landing or a touch on the brakes makes it sound like a precise science nothing could be further from the truth @3much of the language _ _ describe monetary policy @steering the economy to a _ landing @much of the _ describe monetary @
Sample Output
Case 1:YESYESNO
【解题思路】：
kmp算法：
代码：
Problem 1926 填空#include #include #include #include #include #include #include #include #include
暂时没有评论，来抢沙发吧~