Codeforces Round #573 (Div. 2)

浅浅的花香味﹌ 2021-09-29 13:10 268阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>Sloved</th> 
   <th align="center">A</th> 
   <th align="center">B</th> 
   <th align="center">C</th> 
   <th align="center">D</th> 
   <th align="center">E</th> 
   <th align="center">F</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>6/6</td> 
   <td align="center">O</td> 
   <td align="center">O</td> 
   <td align="center">O</td> 
   <td align="center">O</td> 
   <td align="center">Ø</td> 
   <td align="center">Ø</td> 
  </tr> 
 </tbody> 
</table>

*  O for passing during the contest
 *  Ø for passing after the contest
 *  ! for attempted but failed
 *  · for having not attempted yet

## A.Tokitsukaze and Enhancement(0:05,+1) ##

签到题，读题找规律即可

## B.Tokitsukaze and Mahjong(0:24,+3) ##

模拟，注意1m 3m 5m的情况

## C.Tokitsukaze and Discard Items(00:48,+1) ##

直接O(n)遍历模拟即可，不要想复杂

## D.Tokitsukaze, CSL and Stone Game(01:35,+2) ##

考虑几种情况

*  2 2 3和1 2 2，后一种cslnb
 *  计算数的个数大于2的总数，cnt >= 2，则cslnb（包括 3 3 3这种情况）
 *  一些显然得到答案的方案

最后特判完，假如还没有得到结果，则最后的局面应为 0 1 2 3 … n-1，直接作差，%2判断即可

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    const int maxn = 1e5 + 1000;
     
    ll n;
    ll a[maxn];
    int main(int argc, char const *argv[])
    { 
    	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
     
    	cin >> n;
     
    	ll sum = 0;
    	int zero = 0;
    	rep(i,0,n)
    	{ 
    		cin >> a[i];
    		if(a[i] == 0)
    		{ 
    			zero++;
    		}
    		sum += a[i];
    	}
    	if(sum == 0)
    	{ 
    		cout << "cslnb" << endl;
    		return 0;
    	}
     
    	if(zero >= 2)
    	{ 
    		cout << "cslnb" << endl;
    		return 0;	
    	}
     
    	if(n == 1) // judge only
    	{ 
    		if(sum % 2 == 0)
    		{ 
    			cout << "cslnb"<<endl;
    		}
    		else
    		{ 
    			cout << "sjfnb"<<endl;
    		}
    		return 0;
    	}
     
    	sort(a,a+n);
     
    	int cnt = 0;
    	int t = 0;
    	int wz = 0;
    	rep(i,0,n)
    	{ 
    		if(a[i] == a[i+1])
    		{ 
    			cnt++;
    			t = a[i];
    			wz = i;
    		}
    	}
    	if(cnt >= 2)
    	{ 
    		   cout <<"cslnb" << endl;
    		   return 0;
    	}
    	else if(cnt == 1)
    	{ 
    		if(wz == 0 || a[wz-1] < t-1)
    		{ 
    			sum -= (0+n-1)*n/2;
    			if(sum % 2 == 0)
    			{ 
    				cout << "cslnb"<<endl;
    			}
    			else
    			{ 
    				cout << "sjfnb"<<endl;
    			}
    			return 0;
    		}
    		else
    		{ 
    			cout << "cslnb" << endl;
    			return 0;
    		}
    	}
    	else
    	{ 
    		sum -= (0+n-1)*n/2;
    		if(sum % 2 == 0)
    		{ 
    			cout << "cslnb"<<endl;
    		}
    		else
    		{ 
    			cout << "sjfnb"<<endl;
    		}
    	}
    	return 0;

## E.Tokitsukaze and Duel ##

找出第一个和最后一个1，第一个和最后一个0  
sjf胜利的条件很简单，zero2 - zero1 < k || one2- one1 < k  
难点在qls的回合判断  
现在设计一个数组a，元素为zero2 ， zero1 ， one2， one1，并排序

*  已知在qls的回合，qls不可能输，顶多once again

qls胜利，条件为a2-a0 <= k and a3-a1 <= k

*  已经判断了第一回合，则a1和a2不可能同是0或1，即a0和a3为0和1
 *  无论sjf选择哪一段，必包括a1和a2
 *  假设sjf把那一段变成1，qls可以把边缘的0到中间一段变成1，同理假设sjf把那一段变成0，qls可以把边缘的1到中间一段变成0
 *  重点在于无论如何，当满足条件时，sjf无论如何操作都覆盖到了中间的0和1

假设不满足这个条件，则sjf必定可以选择一段不覆盖中间的0和1，qls只能选择once again  
具体要理解清楚可能需要自己举一些例子，或者严格证明一下

## F.Tokitsukaze and Strange Rectangle ##

扫描线+离散化

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    //树状数组
    struct Bit
    { 
        vector<int> a;
        int sz;
        void init(int n)
        { 
            sz=n+5;
            for(int i=1;i<=n+5;i++)
                a.push_back(0);
        }
        int lowbit(int x)
        { 
            return x&(-x);
        }
        int query(int x)
        { 
            int ans = 0;
            for(;x;x-=lowbit(x))ans+=a[x];
            return ans;
        }
        int query(int l ,int r)
        { 
        	return query(r) - query(l-1);
        }
        void update(int x,int v)
        { 
            for(;x<sz;x+=lowbit(x))
                a[x]+=v;
        }
    }bit;
     
    const int maxn = 2e5 + 100;
    VI x[maxn],y; // lsy x, unique y
     
    map<int,int> lsx,lsy,cntx;// id of discrete x,y , number of x
     
    int n;
    int main(int argc, char const *argv[])
    { 
    	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    	cin >> n;
    	bit.init(n);
     
     
    	int sum = 0;
    	rep(i,0,n)
    	{ 
    		int xx,yy;
    		cin >> xx >> yy;
    		if(!lsy.count(yy))
    		{ 
    			lsy[yy] = sum++;
    			y.pb(yy);
    		}
    		x[lsy[yy]].pb(xx);
    		cntx[xx]++;
    	}
    	sort(all(y));
    	// for(auto v : y)
    	// { 
    	// sort(all(x[lsy[v]]));
    	// }
     
    	int s = 0;
    	for(auto v:cntx)
    	{ 
    		s++;
    		lsx[v.fi] = s;
    		bit.update(s,1);
    	}
    	
    	ll ans = 0;
    	for(auto v : y)
    	{ 
    		sort(all(x[lsy[v]]));		
    		int pre = 1; 
    		for(auto u : x[lsy[v]])
    		{ 
    			ans += 1ll * bit.query(pre,lsx[u]) * bit.query(lsx[u],s);
    			//cout << pre << " "<< lsx[u] <<" " << bit.query(pre,lsx[u]) << "---" << endl;
    			//cout << s << " " << bit.query(lsx[u],s) << endl;
    			pre = lsx[u] + 1;
    			cntx[u]--;
    			if(cntx[u] == 0)
    			{ 
    				//cntx.erase(u);
    				bit.update(lsx[u],-1);
    			}													
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }