您當前位置：首頁 > php開源 > 綜合技術 > zoj Capture the Flag 比較難的模擬題

zoj Capture the Flag 比較難的模擬題

來源：程序員人生發布時間：2015-07-28 08:08:48 閱讀次數：3764次

Capture the Flag

Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge

In computer security, Capture the Flag (CTF) is a computer security competition. CTF contests are usually designed to serve as an educational exercise to give participants experience in securing a machine, as well as conducting and reacting to the sort of attacks found in the real world. Reverse-engineering, network sniffing, protocol analysis, system administration, programming, and cryptanalysis are all skills which have been required by prior CTF contests at DEF CON. There are two main styles of capture the flag competitions: attack/defense and jeopardy.

In an attack/defense style competition, each team is given a machine (or a small network) to defend on an isolated network. Teams are scored on both their success in defending their assigned machine and on their success in attacking other team's machines. Depending on the nature of the particular CTF game, teams may either be attempting to take an opponent's flag from their machine or teams may be attempting to plant their own flag on their opponent's machine.

Recently, an attack/defense style competition called MCTF held by Marjar University is coming, and there are N teams which participate in the competition. In the beginning, each team has S points as initial score; during the competition, there are some checkpoints which will renew scores for all teams. The rules of the competition are as follows:

If a team has been attacked for a service P, they will lose N - 1 points. The lost points will be split equally and be added to the team(s) which attacks successfully. For example, there are 4 teams and Team A has been attacked by Team B and Team C, so Team A will lose 3 points, while Team B and Team C each will get 1.5 points.
If a team cannot maintain their service well, they will lose N - 1 points, which will be split equally too and be added to the team(s) which maintains the service well.

The score will be calculated at the checkpoints and then all attacks will be re-calculated. Edward is the organizer of the competition and he needs to write a program to display the scoreboard so the teams can see their scores instantly. But he doesn't know how to write. Please help him!

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains four integers N (2 <= N <= 100) - the number of teams, Q - the number of services (1 <= Q <= 10), S - the initial points (0 <= S <= 100000) and C - the number of checkpoints (1 <= C <= 100).

For each checkpoint, there are several parts:

The first line contains an integer A - the number of the successful attacks. Then A lines follow and each line contains a message:
```
[The No. of the attacker] [The No. of the defender] [The No. of the service]
```
For example, "1 2 3" means the 1^st team attacks the 2^nd team in service 3 successfully. The No. of teams and services are indexed from 1. You should notice that duplicate messages are invalid because of the rules. Just ignore them.
Then there are Q lines and each line contains N integers. The j^th number of the i^th line indicating the j^th team's maintaining status of the i^th service, where 1 means well and 0 means not well.
Finally there is an integer U (0 <= U <= 100), which describing the number of the queries. The following line contains U integers, which means Edward wants to know the score and the ranking of these teams.

Output

For each query L, output the score and the ranking of the L^th team. The relative error or absolute error of the score should be less than 10^⑸. The team with higher score gets higher rank; the teams with the same scores should have the same rank. It is guaranteed that the scores of any two teams are either the same or with a difference greater than 10^⑸.

Sample Input

1 4 2 2500 5 0 1 1 1 1 1 1 1 1 4 1 2 3 4 2 1 2 1 3 2 1 1 1 1 1 1 1 1 1 4 1 2 3 4 1 1 2 2 1 1 1 1 1 1 1 0 4 1 2 3 4 0 0 0 0 0 0 0 0 0 4 1 2 3 4 0 1 1 1 1 1 1 1 1 2 1 4

Sample Output

2500.00000000 1 2500.00000000 1 2500.00000000 1 2500.00000000 1 2501.50000000 1 2497.00000000 4 2501.50000000 1 2500.00000000 3 2505.50000000 1 2495.00000000 4 2502.50000000 2 2497.00000000 3 2499.50000000 1 2489.00000000 4 2496.50000000 2 2491.00000000 3 2499.50000000 1 2491.00000000 3

Hint

For C++ users, kindly use scanf to avoid TLE for huge inputs.

鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5527

題意：

n個隊伍，q臺服務器，s為初始分數，5次操作

每次操作中有A次攻擊

每次攻擊 a b ser，表示 a隊攻擊 b隊，通過服務器ser。疏忽重復出現一樣的 a b ser。

攻擊完后，計算分數要把每臺服務器上的攻擊分開計算。被攻擊的隊伍-（n⑴）分，把這n⑴分平分給攻擊他的隊伍。

然后是q行n列

表示每臺服務器上，n支隊伍有無保護好各自領域。把沒保護好的隊伍扣n⑴分，把扣的總分平分給保護好的隊伍。

然后1個U，詢問U個隊伍的分數和排名，然后輸出。排序的時候注意精度，如 0.123451和0.123452 實際上不相等，但是精度為1e⑸時，算是相等的

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> using namespace std; #include <stack> #include <queue> #include <vector> #include <deque> #include <set> #include <map> using namespace std; #define maxn 505 #define eps 1e⑸ struct nodedef { double point; int id; int rank; }; nodedef nod[110]; int ok[11][110]; int vis[110][110][15]; vector <int> vec[11][110]; int has[110]; int cmp1(nodedef a,nodedef b) { return a.point>b.point; } int cmp2(nodedef a,nodedef b) { return a.id<b.id; } int main() { int t; scanf("%d",&t); while(t--) { int n,q,s,c; scanf("%d%d%d%d",&n,&q,&s,&c); for(int i=1;i<=n;i++) { nod[i].point=s; nod[i].id=i; } while(c--) { int aa; scanf("%d",&aa); memset(vis,0,sizeof vis); for(int i=1;i<=q;i++) { for(int j=1;j<=n;j++) { vec[i][j].clear(); } } for(int i=0;i<aa;i++)//A次服務器攻擊，各個服務器之間是沒有相互影響的，所以ser要開1個維度，然后把攻擊b的所有隊伍存在在1起 { int a,b,ser; scanf("%d %d %d",&a,&b,&ser); if(vis[a][b][ser]==0) //重復的命令去掉 vec[ser][b].push_back(a); vis[a][b][ser]=1; } for(int i=1;i<=q;i++) { for(int j=1;j<=n;j++) { if(vec[i][j].size()) { nod[j].point-=(n⑴); for(int k=0;k<vec[i][j].size();k++)//依照規則，攻擊的人平分這n⑴ 分 { nod[vec[i][j][k]].point+=1.0*(n⑴)/vec[i][j].size(); } } } } for(int i=1;i<=q;i++)//不同服務器直接不相互影響 { for(int j=1;j<=n;j++) { int tem; scanf("%d",&ok[i][j]); } int li=0; int yi=0; for(int j=1;j<=n;j++) { if(ok[i][j]) yi++; else { nod[j].point-=(n⑴); li++; } } for(int j=1;j<=n;j++) { if(ok[i][j]) nod[j].point+=1.0*(n⑴)*li/yi; //把li個被破壞的服務器數*n⑴分平分被yi個保護好的服務器 } } sort(nod+1,nod+1+n,cmp1); nod[1].rank=1; for(int i=2;i<=n;i++) { if((nod[i⑴].point-nod[i].point)<eps)//要注意的地方，由于精度問題，所以這里要<eps //如 0.123451和0.123452 實際上不相等，但是精度為1e⑸時，算是相等的 nod[i].rank=nod[i⑴].rank; else nod[i].rank=i; } int cha; scanf("%d",&cha); sort(nod+1,nod+1+n,cmp2); for(int i=1;i<=cha;i++) { int id; scanf("%d",&id); printf("%f %d ",nod[id].point,nod[id].rank); } } } return 0; }