[CF1244C] The Football Season【数学，思维题，枚举】

25-04-07 5

如果您对[CF1244C]TheFootballSeason【数学，思维题，枚举】感兴趣，那么本文将是一篇不错的选择，我们将为您详在本文中，您将会了解到关于[CF1244C]TheFootballSe

如果您对[CF1244C] The Football Season【数学，思维题，枚举】感兴趣，那么本文将是一篇不错的选择，我们将为您详在本文中，您将会了解到关于[CF1244C] The Football Season【数学，思维题，枚举】的详细内容，并且为您提供关于$CF19A\ World\ Football\ Cup$、10194 - Football (aka Soccer)、Arsenal Football Club Transforms Live Video Backhaul with AWS、C. RationalLee 思维题的有价值信息。

本文目录一览：

[CF1244C] The Football Season【数学，思维题，枚举】
$CF19A\ World\ Football\ Cup$
10194 - Football (aka Soccer)
Arsenal Football Club Transforms Live Video Backhaul with AWS
C. RationalLee 思维题

[CF1244C] The Football Season【数学，思维题，枚举】

Online Judge：Luogu，Codeforces Round #592 (Div. 2) C

Label：数学，思维题，枚举

题目描述

某球队一共打了$n$场比赛，总得分为$p$，已知赢一场得$w$分，平局一场得$d$分，输一场不加分也不减分，问一共赢了几场(x)，平局了几场(y)，输了几场(z)？如果不存在合法方案输出"-1"，如果存在多组可能的方案，任意输出一组(Special Judge)。

也就是任求一组符合条件的非负整数三元组$(x,y,z)$，满足:
\[ x\cdot w+y\cdot d=p \x+y+z=n \]

输入

四个整数$n,p,w,d$。

输出

输出三个整数表示符合条件的三元组，如果不存在，则输出"-1"。

样例

Input#1

30 60 3 1

Output#1

17 9 4

Input#2

10 51 5 4

Output#2

-1

Input#3

20 0 15 5

Output#3

0 0 20

Hint

$1<=n<=10^{12}$，$0<=p<=10^{17}$，$1<=d<w<=10^{15}$。

注意，题目数据保证了$d<w$，也就是赢一场的得分严格大于平局一场的得分。

题解

一开始看题，直接打了个exgcd去解不定方程最小解，结果好像中间会爆long long 就WA掉了。其实仔细读题，根本根本不需要这样搞。

现在需要解一个这样的方程组
\[ x+y+z=n....①\x\cdot w+y\cdot d=p....②\\]
①式可以转化为$x+y<=n$，$z$的大小再根据$x,y$具体调整即可。

假设存在一组二元组$(x,y)$，已经能够满足②式了，现在考虑再构造一组解，使得$x+y$尽量小，能满足①式。

则有
\[ x\cdot w+w\cdot d-w\cdot d+y\cdot d=p\\→(x+d)\cdot w+(y-w)\cdot d=p\\]
也就是说必然还存在一组满足②式的解$(x+d,y-w)$，多次进行这样的操作，可以得到$(x+2d,y-2w)$，$(x+3d,y-3w)$，......，由于需要满足$x>0,y>0,z>0$，必然有一个下限使得此时的$y'<w$，减不动了，可以证明此时的这组解一定是最优的（也就是此时的$x'+y'$最小）。为什么呢，由于题目强调了$w>d$，也就是$x->x'$的增量小于$y->y'$减量，所以此时的$x'+y'$一定最小。

所以只用枚举$y∈[0,w-1]$即可，然后分别带入计算得到此时的$x$，再判一下$x+y<=n$这个条件，如果这个范围内都没有满足条件的解，$y$再往大枚举也不可能出现满足条件的解了。

综上时间复杂度为$O(W)$，$W<=10^5$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
ll n,d;
signed main(){
    cin>>n>>p>>w>>d;
    for(int y=0;y<w;y++){
        int left=p-y*d;
        if(left%w)continue;
        int x=left/w;
        if(x>=0&&x+y<=n){
            printf("%lld %lld %lld\n",x,n-x-y);
            return 0;
        }
    }
    puts("-1");
}

$CF19A\ World\ Football\ Cup$

炒鸡$6$批的模拟题。注意的是输入把握好空格大小写。

根据题目的这句话来排序

积分榜是按照以下原则制作的：胜利一个队得3分，平分1分，失败0分。
首先，球队按积分顺序排在积分榜上，分数相等比较净胜球，净胜球相等比较进球数。

排序的话根据分数净胜球进球数来排序反正就是明白输入之后就很简单了

// score - > win - > ball 分别表示 分数净胜球 进球数

#include <bits/stdc++.h>
#define rep(i,j,n) for(register int i=j;i<=n;i++)
#define Rep(i,j,n) for(register int i=j;i>=n;i--)
#define low(x) x&(-x)
using namespace std ;
typedef long long LL ;
const int inf = INT_MAX >> 1 ;
inline LL In() { LL res(0) , f(1) ; register char c ;
#define gc c = getchar()
    while(isspace(gc)) ; c == ''-'' ? f = - 1 , gc : 0 ;
    while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(gc)) ;
    return res * f ;
#undef gc
}

const int N = 50 + 5 ;
int n ;
struct node {
	string name ;
	int score ;
	int win ;
	int ball ;
}a[N] ;
map < string , int > score , win , ball ;

bool cmp(node x , node y) {
	// score - > win - > ball
	if(x.score != y.score) return x.score > y.score ;
	else {
		if(x.win != y.win) return x.win > y.win ;
		return x.ball > y.ball ;
	}
}
bool cmp2(node x , node y) {
	return x.name < y.name ;
}
inline void Ot() {
	n = In() ;
	rep(i,1,n) {
		cin >> a[i].name ;
		a[i].score = a[i].ball = a[i].win = 0 ;
	}
	rep(i,1,n*(n-1) >> 1) {
		string s1 , s2 ;
		register char c ;
		//scanf("%s-%s %d:%d",&s1,&s2,&_1,&_2) ;
#define gc c = getchar()
		while(isspace(gc)) ;
		s1 += c ;
		while(islower(gc) or isupper(c)) s1 += c ;
		while(islower(gc) or isupper(c)) s2 += c ;
		int x = In() , y = In() ;
		if(x > y) score[s1] += 3 ;
		if(x == y) score[s1] ++ , score[s2] ++ ;
		if(x < y) score[s2] += 3 ;
		win[s1] += (x - y) , win[s2] += (y - x) ;
		ball[s1] += x , ball[s2] += y ;
	}
	rep(i,1,n) {
		a[i].score = score[a[i].name] ;
		a[i].ball = ball[a[i].name] ;
		a[i].win = win[a[i].name] ;
	}
	sort(a+1,a+n+1,cmp) ;
	sort(a+1,a+(n>>1)+1,cmp2) ;
	rep(i,1,(n>>1)) cout << a[i].name << endl ;
}
signed main() {
//  freopen("test.in","r",stdin) ;
    return Ot() , 0 ;
}

10194 - Football (aka Soccer)

题意:
读入各个球队的名字, 和球队之间比赛的进球数, 要求统计各个球队的比赛总场数, 总得分等信息, 按以下优先级顺序进行输出:
1. 最高得分
2. 最多胜利场次
3. 最多净胜球数(进球-失球)
4. 最多进球数
5. 最少比赛场数
6. 球队名字典序, 小的排前面(比较时不区分大小写)
注意: scored 3 goals 指的是进球数为 3, 不是得分 3; 看题目的时候这个理解错了, 纠结了好久, 无从下手.

思路:
1. 读入一行, 按 # 拆分出球队名和进球数.
2. 计算得分, 净胜球等信息.
3. 根据重载的 > 进行排序, 比较规则如题意所示.
4. 按顺序进行输出.

要点:
1. 重载 > 可以是成员函数, 重载 << 时必须是友元函数, 因为其要接收一个 ostream& 的参数. ???
2. 对于 if, for, 如果想不写{}, 那么其一行写完的句子必须简短到可以直接补在 if, for 后面, 形成一行.

题目:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=98&page=show_problem&problem=1135

代码:

# include <iostream>
# include <string>
# include <cstdio>
# include <cstring>
# include <vector>
# include <algorithm>
# include <cctype>
# include <iterator>
# include <assert.h>
# include <map>
using namespace std;

// scored 3 goals 指的是进球数为 3, 不是得分 3 
// 遍历 map
// 重载 <, <<(只支持 friend？)
// distance 取两个 iterator 之间的距离

class TeamRecord {
public:
  TeamRecord(const string& teamName):
    scoreWin_(3), scoreTie_(1), scoreLoss_(0) {
    teamName_ = teamName;

    teamNameUpper_ = teamName_;
    transform(teamName_.begin(), teamName_.end(), 
              teamNameUpper_.begin(), ::toupper);

    win_ = 0;
    tie_ = 0;
    loss_ = 0;
    goalScored_ = 0;
    goalAgainst_ = 0;
  }

  // 羸、平、输
  void win() { ++win_; }
  void tie() { ++tie_; }
  void loss() { ++loss_; }

  // 进、丢球数
  void scored(const int goal) { goalScored_ += goal; }
  void against(const int goal) { goalAgainst_ += goal; }

  // 总分数
  int getPoints() const {
    return win_*scoreWin_ + tie_*scoreTie_ + loss_*scoreLoss_;
  }

  int getWin() const { return win_; }
  int getGoalDifference() const { return goalScored_ - goalAgainst_; } 
  int getGoalScored() const { return goalScored_; }
  int getNumGames() const { return win_ + tie_ + loss_; }
  string getTeamNameUpper() const { return teamNameUpper_; }

  // 转成题目需要的输出
  friend ostream& operator<<(ostream& os, const TeamRecord& tr);

  // 重载 > 符号， 按以下规则
  /*
    Most points earned.
    Most wins.
    Most goal difference (i.e. goals scored - goals against)
    Most goals scored.
    Less games played.
    Lexicographic order. 
  */
  bool operator> (const TeamRecord& right) const {
    if (getPoints() > right.getPoints()) return true;
    if (getPoints() < right.getPoints()) return false;

    if (getWin() > right.getWin()) return true;
    if (getWin() < right.getWin()) return false;

    if (getGoalDifference() > right.getGoalDifference()) return true;
    if (getGoalDifference() < right.getGoalDifference()) return false;

    if (getGoalScored() > right.getGoalScored()) return true;
    if (getGoalScored() < right.getGoalScored()) return false;

    // 这里是不同的，要参赛参少的排前面
    if (getNumGames() < right.getNumGames()) return true;
    if (getNumGames() > right.getNumGames()) return false;

    // 名字比较时不区分大小写, 按字典序，小的排前面
    return (getTeamNameUpper() < right.getTeamNameUpper());
  } 

private:
  string teamName_;
  string teamNameUpper_;
  int win_;
  int tie_;
  int loss_;

  int goalScored_ ;     // 进球数
  int goalAgainst_;     // 丢球数

  const int scoreWin_;  // 羸了 3 分
  const int scoreTie_;  // 平了 1 分
  const int scoreLoss_; // 输了 0 分
};


ostream& operator<<(ostream& os, const TeamRecord& tr) {
  char temp[500];
  sprintf(temp, "%s %dp, %dg (%d-%d-%d), %dgd (%d-%d)", 
          tr.teamName_.c_str(),
          tr.getPoints(),
          tr.win_ + tr.tie_ + tr.loss_,
          tr.win_,
          tr.tie_,
          tr.loss_,
          tr.goalScored_ - tr.goalAgainst_,
          tr.goalScored_,
          tr.goalAgainst_);

  os << temp;
  return os;
}



// 比较两个 TeamRecord
bool greaterRank(const TeamRecord* tr1, const TeamRecord* tr2) {
  return (*tr1) > (*tr2);
}


// 将 Brazil#2@1#Scotland 格式中的 teamName, goals 分解出来
void splitTeamGoals(const string& line, 
                    map<string, TeamRecord*>& teamRecords) {

  size_t pos1 = line.find("#", 0);
  size_t pos2 = line.find("@", 0);
  size_t pos3 = line.find("#", pos2);

  string teamName1 = line.substr(0, pos1);
  int goals1 = atoi(line.substr(pos1+1, pos2-pos1-1).c_str());

  string teamName2 = line.substr(pos3+1, line.size()-pos3-1);
  int goals2 = atoi(line.substr(pos2+1, pos3-pos2-1).c_str());

  TeamRecord* tr1 = teamRecords[teamName1];
  TeamRecord* tr2 = teamRecords[teamName2];

  if (goals1 > goals2) {          // 羸
    tr1->win();
    tr2->loss();
  } else if (goals1 < goals2) {   // 负
    tr1->loss();
    tr2->win();
  } else {                        // 平
    tr1->tie();
    tr2->tie();
  }

  // 进球记录
  tr1->scored(goals1);
  tr1->against(goals2);
  tr2->scored(goals2);
  tr2->against(goals1);
}



int main(int argc, char const *argv[])
{
  #ifndef ONLINE_JUDGE
    freopen("10194_i.txt", "r", stdin);  
    freopen("10194_o.txt", "w", stdout); 
  #endif
 
  int numTournament;
  cin >> numTournament;
  cin.ignore();           // cin 后接 getline, 一定要有这个

  while (numTournament--) {
    string tournamentName;
    getline(cin, tournamentName);
    cout << tournamentName << endl;

    // 读入球队名
    int numTeams;
    cin >> numTeams;
    cin.ignore();

    vector<string> teamNames;
    map<string, TeamRecord*> teamRecords;
    while (numTeams--) {
      string teamName;
      getline(cin, teamName);

      teamNames.push_back(teamName);

      TeamRecord* tr = new TeamRecord(teamName);
      teamRecords[teamName] = tr;
    }

    // 读入并分析比赛记录
    int numGames;
    cin >> numGames;
    cin.ignore();

    while (numGames--) {
      string line;
      getline(cin, line);

      splitTeamGoals(line, teamRecords);
    }

    vector<TeamRecord*> sortedTeamRecords;
    map<string, TeamRecord*>::iterator it;
    for (it = teamRecords.begin(); it != teamRecords.end(); ++it) {
      TeamRecord* tr = it->second;
      sortedTeamRecords.push_back(tr);
    }

    // 使用自定义函数进行排序 
    sort(sortedTeamRecords.begin(), sortedTeamRecords.end(), 
         greaterRank);

    int ordTeam = 0;
    vector<TeamRecord*>::iterator it1;
    for (it1 = sortedTeamRecords.begin(); 
         it1 != sortedTeamRecords.end(); ++it1) {

      cout << ++ordTeam << ") " << **it1 << endl;
      delete (*it1);      // 输出后就可以释放空间了
    }

    if (numTournament > 0)  // 最后不能再输出 回车，否则 WA
      cout << endl;
  }

  return 0;
}

环境: C++ 4.5.3 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE

Arsenal Football Club Transforms Live Video Backhaul with AWS

https://amazonaws-china.com/blogs/media/arsenal-football-club-transforms-live-video-backhaul-with-aws/

Fisheye lens shot of the Arsenal Football Stadium

Since its founding in 1886, UK-based Arsenal Football Club has garnered an estimated fanbase of more than 100 million worldwide, and today, social media and digital video play a crucial role in engaging those followers. Video coverage of ‘friendlies’ matches, in particular, has become popular with their fans across the world. To complement its primary path for video backhaul for these productions, the club recently deployed AWS Elemental MediaConnect to live stream a match against the Colorado Rapids Major League Soccer (MLS) team.

John Dollin, Senior Product and Engineering Manager, Arsenal F.C., shared, “70 percent of Arsenal’s online audience originates from outside of the U.K., and they don’t always have access to matches, so it’s crucial that we develop programming for matches like the one against the Colorado Rapids that we can share with our broadcast rights holders and across our website, apps, and social channels before, during and after the match to keep them up to speed.”

Screenshot of the Arsenal web interface displaying a match report between the Colorado Rapids and Arsenal

Arsenal’s partner, ‘The Switch,’ provided live stadium video contribution for the Arsenal vs. Colorado Rapids feed from Dick’s Sporting Goods Park in Colorado to Emirates Stadium in London via a 15Mbit/s IP link. A new AWS Elemental Live encoder in Colorado was fed an identical video source for contribution to the cloud using the AWS Elemental MediaConnect video transport service, enabling transatlantic backhaul via the AWS network at 40Mbit/s. Arsenal then decoded the IP-based feed in its London facility to HD-SDI baseband for onward production and local distribution to broadcast rights holders.

After a successful run for the Colorado Rapids match, Arsenal is exploring how it might expand its AWS-backed workflow to support weekly deliverables to exclusive rights holders. The club is also looking to Amazon Simple Storage Service (Amazon S3) as an archival and backup option to complement its on-premises workflows.

“We were impressed by how simple it was to set up and deploy a live video backhaul stream from the USA to London using AWS Elemental MediaConnect,” Dollin added. “The stream was as reliable as our primary fibre path, cost significantly less than fibre or satellite, and was better quality. We see significant potential in this workflow to ensure fans and commercial partners around the world can access our games and supporting content with greater flexibility and lower costs for us.”

C. RationalLee 思维题

题意

　　给你n个数字，要求把它们分成k组，每组w[i]个，ans为每组的最小值加最大值的总和。

思路

　　很容易看出，如果一组只有一个人，那么把尽可能较大的分给他，最小值和最大值都会大，ans也会大，所有我们先把大的数分给那些只有一个人的组。

　　考虑剩下的情况，现在每组的最大值都是确认的(较大的每组一个)，那么我们需要把每组的最小值尽可能地提高，所以我们依次把一个最大值，w[cnt]-1个小值分给cnt号组，cnt从k到1，这样就能使之后的组的最小值尽可能高。

AC代码

include<iostream>

include<algorithm>

using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int t,n,k;
int a[maxn],w[maxn];
ll ans;
int main()
{

cin>>t;
while(t--){
    cin>>n>>k;
    ans=0;
    for(int i=1;i<=n;i++)
        cin>>a\[i\];
    for(int i=1;i<=k;i++)
        cin>>w\[i\];
    sort(a+1,a+1+n);
    sort(w+1,w+1+k);
    int cnt=1;
    while(w\[cnt\]==1){
        ans+=a\[n\]\*2;
        n--;
        cnt++;
    }
    int l=1,r=n;
    while(cnt<=k){
        ans+=a\[l\]+a\[r\];
        l+=w\[k\]-1;
        k--;
        r--;
    }
    cout<<ans<<''\\n'';
}
return 0;

}

关于[CF1244C] The Football Season【数学，思维题，枚举】的问题我们已经讲解完毕，感谢您的阅读，如果还想了解更多关于$CF19A\ World\ Football\ Cup$、10194 - Football (aka Soccer)、Arsenal Football Club Transforms Live Video Backhaul with AWS、C. RationalLee 思维题等相关内容，可以在本站寻找。

本文标签：