傳送門題面：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 byMarjar University is coming, and there are N teams whichparticipate in the competition. In the beginning, each team has Spoints as initial score; during the competition, there are some checkpointswhich will renew scores for all teams. The rules of the competition are asfollows:

• 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^-5. 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^-5.

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.

? ? 題目描述：有n個人進行黑客比賽。他們的初始分數為s，他們有Q臺機器要進行攻擊和防守，要進行C個回個的較量。每個回合互相都可以進行攻擊，當第i個人被攻擊時，他將會扣除n-1點分數，而攻擊第i個人的所有人可以平均分得著n-1點分數。

????每個回合黑客們也要進行對Q個機器的維護，對于第i個機器，第j個人成功維護輸入1，未成功維護輸入0，未成功維護的人將扣除n-1點分數，這n-1點分數由成功維護好了第i個機器的人所評分。????最后有U個詢問，每個詢問有一個輸入id輸出第id個人的分數和排名。

? ? 題目分析：這題就是一個大模擬。（事實上模擬出的難度并不算高（就是題目比較長））。????理解了題意之后我們可以知道，這道題有三個操作，第一個是要維護攻擊時的分數分配。對于這個問題，我們可以開一個三維的vis數組vis[i][j][k]，記錄第i個人攻擊第j個人的第k個服務器，之后枚舉即可。? ? 第二個是要維護維護Q個機器時的分數分配。對于這個問題，因為要統計0和1的個數，我們可以開兩個數組記錄下0和1的編號即可（也可以用vector去記錄，這樣方便一些）

? ? 第三個是要維護分數更改后的排名。這個我們可以重載兩次sort的運算符（第一次使之按數值的大小降序排序，第二次按id的大小升序排）因為題面要求精度要小于1e-5，所以在排名的時候只要把滿足兩個數相減小于1e-5的看作相等即可。? ? 最后保留八位小數輸出即可！

? ? 整體上不算難想，就是實現上有點繁瑣，對于這種大模擬，估計只能多練了。つ﹏?? ? 代碼如下：????#include <bits/stdc++.h> #define maxn 105 #define ESP 1e-5 using namespace std; struct name{int id;double sum;int ranks; }q[maxn]; bool vis[maxn][maxn][maxn]; bool cmp(name a,name b){return a.sum>b.sum; } bool cmp2(name a,name b){return a.id<b.id; } int main() {//freopen("in.txt","r",stdin);int t;scanf("%d",&t);while(t--){int n,Q,c;double s;scanf("%d%d%lf%d",&n,&Q,&s,&c);for(int i=1;i<=n;i++){q[i].id=i;q[i].ranks=1;q[i].sum=s;}while(c--){int A;memset(vis,0,sizeof(vis));scanf("%d",&A);for(int i=0;i<A;i++){int att,def,sef;scanf("%d%d%d",&att,&def,&sef);vis[att][def][sef]=1;}for(int i=1;i<=Q;i++){for(int j=1;j<=n;j++){int cnt=0;for(int k=1;k<=n;k++){if(vis[k][j][i]) cnt++;}if(!cnt) continue;q[j].sum-=n-1;double add_scr=(n-1)*1.0/cnt;for(int k=1;k<=n;k++){if(vis[k][j][i]) q[k].sum+=add_scr;}}}for(int i=1;i<=Q;i++){vector<int> one;vector<int> zero;for(int j=1;j<=n;j++){int tmp;scanf("%d",&tmp);if(tmp) one.push_back(j);else zero.push_back(j);}double mins=0;for(int j=0;j<zero.size();j++){q[zero[j]].sum-=n-1;mins+=n-1;}mins=1.0*mins/one.size();for(int j=0;j<one.size();j++){q[one[j]].sum+=mins;}}int U;scanf("%d",&U);sort(q+1,q+1+n,cmp);q[1].ranks=1;int rankp=1;for(int i=2;i<=n;i++){rankp++;if(q[i-1].sum-q[i].sum<=ESP){q[i].ranks=q[i-1].ranks;}else q[i].ranks=rankp;}sort(q+1,q+1+n,cmp2);while(U--){int x;scanf("%d",&x);printf("%.8f %d\n",q[x].sum,q[x].ranks);}}}return 0; }

轉載于:https://www.cnblogs.com/Chen-Jr/p/11007296.html

總結

以上是生活随笔為你收集整理的ZOJ 3879（大模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。