第六次训练：Codeforces Round #595 (Div. 3)

1.Codeforces Round #595 (Div. 3) C1

题意：给定一个数n，求一个不小于n的数，并且这个数能够表示为3的幂的和的形式，并且3每一次幂都只能出现一次。
　　先按幂从小到大顺序累加3的次方，当大于等于n时看能不能减去一些已经加上的3的幂，以得到最小的值。注意，需要从大往小减，以保证最小。（因为累加x的1、2、3、、、n次方会小于x的n+1次方）

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
const ll mod=1e9+7;
#define PI acos(-1.0)
const int maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,a[600],ans,aans;
ll cal(ll,ll);
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
        cin>>n;
        ans=0;
        for(int i=0;;i++)
        {
            ans+=cal(3,i);
            if(ans>=n)  { aans=i; break; }
        }
        for(int i=aans;i>=0;i--)
        if(ans-cal(3,i)>=n) ans-=cal(3,i);
        cout<<ans<<endl;
    }
    return 0;
}
ll cal(ll a,ll b)//��������a^b
{
    ll cnt=1;
    while(b)
    {
        if(b%2)
        cnt=cnt*a%mod;
        b/=2;
        a=a*a%mod;
    }
    return cnt;
}

2.Codeforces Round #595 (Div. 3) A

题意：有I个学生，每个学生对应自己能力ai，分组使得每组中不会有学生的能力ai是连续的。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const int maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,a[200],flag;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        sort(a+1,a+n+1);
        flag=0;
        for(int i=1;i<n;i++)
        if(a[i]+1==a[i+1]) flag=1;
        if(flag) cout<<"2"<<endl;
        else cout<<"1"<<endl;
    }
    return 0;
}

3.Codeforces Round #595 (Div. 3) D1

题意：给定n条线段数轴上的左右值，求最少删除几条线段能够保证不超过k个点被线段覆盖，输出这几条线段的输入顺序。
　　很眼熟的题目，很类似以前做的一个整数区间的题目，虽然条件不一样，但异曲同工。

#include <bits/stdc++.h>

using namespace std;

const int N = 250;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> segs(n);
	vector<int> cnt(N);
	for (int i = 0; i < n; ++i) {
		cin >> segs[i].first >> segs[i].second;
		++cnt[segs[i].first];
		--cnt[segs[i].second + 1];
	}
	
	for (int i = 0; i + 1 < N; ++i) {
		cnt[i + 1] += cnt[i];
	}
	
	vector<int> ans(n);
	for (int i = 0; i < N; ++i) {
		while (cnt[i] > k) {
			int pos = -1;
			for (int p = 0; p < n; ++p) {
				if (!ans[p] && (segs[p].first <= i && i <= segs[p].second) && (pos == -1 || segs[p].second > segs[pos].second)) {
					pos = p;
				}
			}
			assert(pos != -1);
			for (int j = segs[pos].first; j <= segs[pos].second; ++j) {
				--cnt[j];
			}
			ans[pos] = 1;
		}
	}
	
	cout << accumulate(ans.begin(), ans.end(), 0) << endl;
	for (int i = 0; i < n; ++i) {
		if (ans[i]) cout << i + 1 << " ";
	}
	cout << endl;
	
	return 0;
}

4.Codeforces Round #595 (Div. 3) B1

题意：有n个人，每个人都有一本不一样的书，它可以把自己的书给第ai个人，当那个人拿到后也可以继续给他对应的人，求每个人需要传几次才能回到自己手上。
　　简单的情况下人数少，所以一个一个单独直接暴力解题就可以。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const int maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,a[220],ans;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            ans=0;
            for(int j=i;;)
            {
                if(a[j]==i) { cout<<++ans<<" "; break; }
                else { ans++; j=a[j]; }
            }
        }
        cout<<endl;
    }
    return 0;
}

5.Codeforces Round #595 (Div. 3) C2

题意：给定一个数n，求一个不小于n的数，并且这个数能够表示为3的幂的和的形式，并且3每一次幂都只能出现一次。
　　升华的题解。看n在三进制下，符合要求的数就是所有位数不是2的数。那么就只要将n变大到符合要求即可。只要三进制下有2，就找到最大位的那个2，然后找到它左边最近的的一个0变成1，如果没有0就加一位为1。再将这个1后面的所有为换成0，输出这个数十进制形式。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string change(ll x)
{
    if(x==0) return "0";
    string res="";
    while(x)
    {
        res+=char(x%3+'0');
        x/=3;
    }
    res+="0";
    reverse(res.begin(),res.end());
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        ll n;
        cin>>n;
        string now=change(n);
        // cout<<n<<" base3 "<<now<<endl;
        bool f=0;
        for(char v:now)
        {
            if(v=='2') f=1;
        }
        if(!f)
        {
            cout<<n<<endl;continue;
        }
        int len=(int)now.length();
        ll ans=0;
        int id;
        for(int i=0;i<len;i++)
        {
            if(now[i]=='2')
            {
                id=i;break;
            }
        }
        int id2;
        for(int i=id;i>=0;i--)
        {
            if(now[i]=='0')
            {
                id2=i;
                 now[i]='1';break;
            }
        }
        for(int i=id2+1;i<len;i++) now[i]='0';
        for(char c:now)
        {
            ans=ans*3+(c-'0');
        }
        cout<<ans<<endl;
    }
    return 0;
}

6.Codeforces Round #595 (Div. 3) D2

题意：给定n条线段数轴上的左右值，求最少删除几条线段能够保证不超过k个点被线段覆盖，输出这几条线段的输入顺序。

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> segs(n);
	vector<int> cnt(N);
	vector<vector<int>> ev(N);
	for (int i = 0; i < n; ++i) {
		cin >> segs[i].first >> segs[i].second;
		++cnt[segs[i].first];
		--cnt[segs[i].second + 1];
		ev[segs[i].first].push_back(i + 1);
		ev[segs[i].second + 1].push_back(-i - 1);
	}
	
	for (int i = 0; i + 1 < N; ++i) {
		cnt[i + 1] += cnt[i];
	}
	
	vector<int> ans(n), sub(N);
	set<pair<int, int>> curSegs;
	int curSub = 0;																																				
	for (int i = 0; i < N; ++i) {
		curSub += sub[i];
		for (auto it : ev[i]) {
			if (it > 0) {
				curSegs.insert(make_pair(segs[it - 1].second, it - 1));
			} else {
				auto iter = curSegs.find(make_pair(segs[-it - 1].second, -it - 1));
				if (iter != curSegs.end()) curSegs.erase(iter);
			}
		}
		while (cnt[i] - curSub > k) {
			assert(!curSegs.empty());
			int pos = curSegs.rbegin()->second;
			curSegs.erase(prev(curSegs.end()));
			++curSub;
			--sub[segs[pos].second + 1];
			ans[pos] = 1;
		}
	}
	
	cout << accumulate(ans.begin(), ans.end(), 0) << endl;
	for (int i = 0; i < n; ++i) {
		if (ans[i]) cout << i + 1 << " ";
	}
	cout << endl;
	
	return 0;
}

7.Codeforces Round #595 (Div. 3) B2

题意：有n个人，每个人都有一本不一样的书，它可以把自己的书给第ai个人，当那个人拿到后也可以继续给他对应的人，求每个人需要传几次才能回到自己手上。
　　看官方题解确实我也是这么想的，因为某个人传给的哪个人是固定的，所以当传给一个已经计算过的人会重复很多工作。不过，我写了半天也没实现出来，也没找出哪错了，看官方给出的代码，原来用vector可以这么省事。

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> p(n);
		for (int j = 0; j < n; ++j) {
			cin >> p[j];
			--p[j];
		}
		vector<int> used(n);
		vector<int> ans(n);
		for (int j = 0; j < n; ++j) {
			if (!used[j]) {
				vector<int> cur;
				while (!used[j]) {
					cur.push_back(j);
					used[j] = true;
					j = p[j];
				}
				for (auto el : cur) ans[el] = cur.size();
			}
		}
		for (int j = 0; j < n; ++j) cout << ans[j] << " ";
		cout << endl;
	}
	
	return 0;
}