2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019)

摘要：

分数变化不会超过倍。请参阅代码：code/**作者：heyuhhh*创建时间：2020/5/2816:33:31*/#include#include#include#include#include#include#include#include#include＜queue˃#include«iomanip˃#include#include#include#include#defineMPMmake_pair#definefifirst#definesecond#definebpush_back#definesz.size（）#definineall.begin（）,. end（）#defineINF0x3f3f3f#defineLocal#ifdefLocal#definedbgdo｛cout˂˂#args˂”；err；｝whilewider（）{std:：cout˂˃n˃˃w；forrk[i]=1；对于{intk；cin˃˃k；对于{int x；cin˃+x；int&p=point[x]；num[p]+=11l**rk[p]；lazy[p]=i；++rk[p]，sum[x]+=num[p]-pre[x]对于{int&p=point[i]；num[p]+=11l**rk[p]；lazy[p]=w；sum[i]+=num[p]-pre[i]；doubleans=1.0*sum[i]/w；cout˂˂ans˂˂''；}intmain（）｛ios:：sync_with_stdio；cin.tie；cout.tie；cout˂˂fixed˂˂setprecision；run（）；return0；｝还有另一种更巧妙的方法：每当一个人的分数由他的分数决定时，他给这些分数为的人带来的影响是持久的，甚至可能持续到比赛结束（我在说什么？此外，他可以赶上一些当前分数为（x+1）的人，其余的人仍然可以给他带来影响。当一个人的分数变成（x+1）时，他们赶上了一些人，因此这些人暂时对他没有影响，因此他们之前的贡献将被扣除。

Contest Info

传送门

Solved	A	B	C	D	E	F	G	H	I	J	K
7 / 11	Ø	-	O	-	O	O	O	Ø	O	-	-

O 在比赛中通过
Ø 赛后通过
! 尝试了但是失败了
- 没有尝试

Solutions

A. Average Rank

题意：
有(n)个人，(w)周，初始每个人为(0)分。
之后每周会给定一些人，他们的分数会增加(1)分，并且所有人的名次也会发生改变（初始所有人的排名都为(1)）。
分数的改变不会超过(10^6)次。
最后问每个人在(w)周内排名的平均值为多少，除开初始状态。

思路：
挺考察思维的一个题，显然我们要利用好改变次数不超过(10^6)这个条件。
分析一个人的分数由(x ightarrow x+1)所带来的影响：显然他的排名会归类到分数为(x+1)的那一档，并且其余分数为(x)的人排名会(+1)。
那么我们对每一类的分数做一个标记，表示当前已经增加了多少，同时还维护一下上一次增加的时间，我们只用在发生改变的时候进行累加即可，而不是每一次改变把这些人都算一次（类似于lazy标记，最后一次我们会将所有标记下放）。
还有些细节，计算贡献时除开时间，还有当前这个人到达(x)分段时的答案，这样才能维护变化。
详见代码：

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/5/28 16:33:31
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#include <functional>
#include <numeric>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5;
 
int rk[N], point[N], lazy[N];
ll sum[N], num[N], pre[N];
 
void run() {
    int n, w; cin >> n >> w;
    for (int i = 0; i < N; i++) rk[i] = 1;
    for (int i = 0; i < w; i++) {
        int k; cin >> k;
        for (int j = 0; j < k; j++) {
            int x; cin >> x;
            int& p = point[x];
            num[p] += 1ll * (i - lazy[p]) * rk[p];
            lazy[p] = i;
            ++rk[p];
            sum[x] += num[p] - pre[x];
            
            ++p;
            num[p] += 1ll * (i - lazy[p]) * rk[p];
            lazy[p] = i;
            pre[x] = num[p];
        }
    }
    for (int i = 1; i <= n; i++) {
        int& p = point[i];
        num[p] += 1ll * (w - lazy[p]) * rk[p];
        lazy[p] = w;
        sum[i] += num[p] - pre[i];
        double ans = 1.0 * sum[i] / w;
        cout << ans << '
';
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

还有另外一种更加巧妙的方法：每次一个人的分数由(x ightarrow x+1)，他给分数为(x)的这些人所带来的影响是久远的，甚至可能持续到比赛结束~~（我在说什么？）~~。并且，他能够追上一些人，这些人目前的分数为(x+1)，其余的人依旧能给他带来影响。
简单来说，就是维护分数(>x)的人的个数，假设为(k)，那么分数(=x)的人的排名就为(k+1)，如果现在分数为(x)的一些人不思进取，前面的每个人始终给他排名(+1)。我们直接维护这个值。当一个人分数变为(x+1)时，追上了一些人，那么这些人对他暂时没影响了，所以之前他们的贡献会被减去。
说起来挺不好说的，可以看看代码，比较清晰，注意的是还是需要维护一个之前的值，这样才能反映出变化：

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/5/28 15:51:27
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#include <functional>
#include <numeric>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5;
 
int cnt[N];
ll lazy[N], sum[N], pre[N];
int point[N];
 
void run() {
    int n, w; cin >> n >> w;
    cnt[0] = n;
    lazy[0] = w;
    for (int i = 0; i < w; i++) {
        int k; cin >> k;
        for (int j = 1; j <= k; j++) {
            int x; cin >> x;
            int& p = point[x];
            sum[x] += lazy[p] - 1ll * cnt[p + 1] * (w - i) - pre[x];
            lazy[p] += w - i;
            
            --cnt[p];
            ++cnt[++p];
            pre[x] = lazy[p];
        }
    }
    for (int i = 1; i <= n; i++) {
        int p = point[i];
        sum[i] += lazy[p] - pre[i];
        double ans = 1.0 * sum[i] / w;
        cout << ans << '
';
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

C. Canvas Line

贪心。注意下特殊case。

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/5/26 14:56:02
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#include <functional>
#include <numeric>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e4 + 5;
 
int n;
struct node {
    int l, r;
} a[N];
 
int p;
int x[N], cnt[N];
 
void run() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r;
    }
    cin >> p;
    for (int i = 1; i <= p; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= p; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[j].l <= x[i] && x[i] <= a[j].r) {
                ++cnt[j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (cnt[i] > 2) {
            cout << "impossible" << '
';
            return;
        }
    }
    vector <int> ans;
    for (int i = 1; i <= n; i++) if (cnt[i] == 0) {
        int p1 = a[i].l, p2 = a[i].r;
        if (i - 1 && a[i - 1].r == p1) {
            if (cnt[i - 1] == 2) ++p1;
            else ++cnt[i - 1];
        }
        if (a[i + 1].l == p2) {
            if (cnt[i + 1] == 2) --p2;
            else ++cnt[i + 1];
        }
        ans.push_back(p1);
        ans.push_back(p2);
        x[++p] = p1, x[++p] = p2;
        cnt[i] = 2;
    }
    for (int i = 1; i <= n; i++) if (cnt[i] == 1) {
        int p1 = a[i].r;
        for (int j = 1; j <= p; j++) {
            if (p1 == x[j]) {
                --p1; break;
            }
        }
        if (a[i + 1].l == p1) {
            if (cnt[i + 1] == 2) --p1;
            else ++cnt[i + 1];
        }
        for (int j = 1; j <= p; j++) {
            if (p1 == x[j]) {
                --p1; break;
            }
        }       
        ans.push_back(p1);
        x[++p] = p1;
    }
    sort(all(ans));
    cout << sz(ans) << '
';
    for (int i = 0; i < sz(ans); i++) {
        cout << ans[i] << ' ';
    }
    cout << '
';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

E. Expeditious Cubing

签到。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
int main() {
	int a[4];
	for(int i=0; i<4; i++) {
		int b,c;
		scanf("%d.%d", &b, &c);
		a[i]=b*100+c;
	}
	sort(a,a+4);
	int t;
	{
		int b,c;
		scanf("%d.%d", &b, &c);
		t=b*100+c;
	}
	t*=3;
	int s;
	s=a[1]+a[2]+a[3];
	if(s<=t) puts("infinite");
	else {
		int k=t-a[1]-a[2];
		if(k>=a[0]) printf("%d.%02d
", k/100, k%100);
		else puts("impossible");
	}
}

F. Firetrucks Are Red

最小生成树。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
const int MAXN = 2e5 + 5, MAXM = 4e5 + 5, BOUND = 2e5, MOD = 1e9+7, INF = 0x3f3f3f3f, base = 10000;
const int inv2 = (MOD + 1) >> 1;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0), eps = 1e-9;
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define lc(x) ch[x][0]
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define rc(x) ch[x][1]
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fi first
#define se second
#define MP std::make_pair
#define ri register int
//#define sz(a) int((a).size())
const int N = 2e5,M = (1<<20);
inline int add(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}
inline int dec(int a, int b) {return a < b ? a - b + MOD : a - b;}
inline int mul(int a, int b) {return 1ll * a * b % MOD;}
template <typename T>
inline void cmin(T &a,T b){a = min(a,b);}
template <typename T>
inline void cmax(T &a,T b){a = max(a,b);}
ll qpow(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1,a=a*a%MOD)if(b&1)ans=ans*a%MOD;
    return ans;
}
mt19937 mrand(random_device{}());
vi G[MAXN],G2[MAXN];
int v[MAXN],fa[MAXN];
struct nod{
    int a,b,c;
};
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void run(){
    int n; cin>>n;
    int len=0;
    rep(i,1,n){
        int m;cin>>m;
        while(m--){
            int x; cin>>x;
            G[i].push_back(x);
            v[++len] = x;
        }
    }
    sort(v+1,v+1+len);
    len = unique(v+1,v+1+len) - v-1;
    rep(i,1,n){
        for(int &x:G[i]){
            x = lower_bound(v+1,v+1+len,x)-v;
            G2[x].push_back(i);
        }
    }
    vector<nod> ans;
    rep(i,1,n)fa[i]=i;
    rep(i,1,len){
        for(int j=1;j<sz(G2[i]);j++){
            int x = find(G2[i][j]), y = find(G2[i][j-1]);
            if(x!=y){
                fa[x]=y;
                ans.push_back({G2[i][j-1],G2[i][j],v[i]});
            }
        }
    }
    if(sz(ans)!=n-1){
        cout<<"impossible
";
        return ;
    }
    for(int i=0;i<sz(ans);i++){
        cout<<ans[i].a<<' '<<ans[i].b<<' '<<ans[i].c<<'
';
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int _=1;
    while(_--)run();
    return 0;
}

G. Gnoll Hypothesis

概率题。简单推一推即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef long double ld;
const int MAXN = 1e3 + 5, MAXM = 4e5 + 5, BOUND = 2e5, MOD = 1e9+7, INF = 0x3f3f3f3f, base = 10000;
const int inv2 = (MOD + 1) >> 1;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0), eps = 1e-9;
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define lc(x) ch[x][0]
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define rc(x) ch[x][1]
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fi first
#define se second
#define MP std::make_pair
#define ri register int
//#define sz(a) int((a).size())
const int N = 2e5,M = (1<<20);
inline int add(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}
inline int dec(int a, int b) {return a < b ? a - b + MOD : a - b;}
inline int mul(int a, int b) {return 1ll * a * b % MOD;}
template <typename T>
inline void cmin(T &a,T b){a = min(a,b);}
template <typename T>
inline void cmax(T &a,T b){a = max(a,b);}
ll qpow(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1,a=a*a%MOD)if(b&1)ans=ans*a%MOD;
    return ans;
}
mt19937 mrand(random_device{}());
ld p[MAXN],co[MAXN];
void run(){
    int n,k;cin>>n>>k;
    rep(i,0,n-1)cin>>p[i],p[i+n]=p[i];
    if(n==1){
        cout<<"100
";
        return ;
    }
    if(k==1){
        rep(i,0,n-1)printf("%.7Lf%c",(db)100/n," 
"[i==n-1]);
        return ;
    }
    if(n==2){
        if(k==2){
            rep(i,0,n-1)cout<<p[i]<<" 
"[i==n-1];
        }else{
            cout<<"50 50
";
        }
        return ;
    }
    co[0] = (db)k*(k-1)/n/(n-1);
    rep(j,1,n-k)co[j] = co[j-1]*(db)(n-k-j+1)/(n-j-1);
    rep(i,0,n-1){
        db ans=p[i]*co[0],sum=p[i];
        rep(j,1,n-k){
            sum += p[n+i-j];
            ans += sum * co[j];
        }
        printf("%.7Lf%c",ans," 
"[i==n-1]);
    }
}
int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    int _=1;
    while(_--)run();
    return 0;
}

H. Height Profile

题意：
给定(a_{1,2...,n})，其中(a_i)表示高度。
后有(k)组询问，每组询问给定一个(g)，询问斜率不小于(g)的最大水平长度为多少。
图片类似于下图：
2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019)第1张

思路：
就是要求(frac{a_j-a_i}{j-i}geq g)，转化一下即为(a_j-gjgeq a_i-gi)。
那么我们确定了(g)，将每个数减去(gi)，之后排序即可解决问题。
注意一点细节，就是最后的端点可能不为整数，会向斜率较大的一方延伸一部分，这里我们二分一下就行。当然也可以直接用差值比例计算，比较巧妙。
注意一下最后会将(g)乘以一个(10)变为整数，直接乘可能精度会有误差，比如(1.0)在计算机中可能会表示为(0.9999..)，但乘(10)取整就有误差了（当然这只是举个例子）。
二分的话比较繁琐，细节见代码：

Code

I. Inverted Deck

模拟一下找区间就行。

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/5/26 14:12:02
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#include <functional>
#include <numeric>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5;
 
int a[N];
 
void run() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            l = i - 1;
            while (l && a[l] == a[l - 1]) --l;
            break;
        }
    }
    for (int i = n - 1; i; i--) {
        if (a[i] < a[i - 1]) {
            r = i;
            while (r + 1 < n && a[r] == a[r + 1]) ++r;
            break;
        }
    }
    if (l <= r) reverse(a + l, a + r + 1);
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            cout << "impossible" << '
';
            return;
        }
    }
    ++l, ++r;
    cout << l << ' ' << r << '
';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019)

Contest Info

Solutions

A. Average Rank

C. Canvas Line

E. Expeditious Cubing

F. Firetrucks Are Red

G. Gnoll Hypothesis

H. Height Profile

I. Inverted Deck

相关文章

访问vector元素方法的效率比较（转）

windows下开多个CMD窗口多个进程输出

zbar配置

C++风格与C风格文件读写效率测试-vs2015,vs2017

【C++】map容器的用法

c++ 动态判断基类指针指向的子类类型（typeid）

最新文章

随机推荐

思享工具箱导航

JSON工具

格式化转换

加解密编码

文本数字

网络

站长

计算

其他

对照列表