7.15

我是个菜鸡.

232人浏览 · 2020-07-15 16:17:12

我是个菜鸡. · 2020-07-15 16:17:12 发布

A - A CodeForces - 1272C

题意：给你串s，再给你几个字母，你们用这几个字符能组成几个s的连续的子串。
思路：首先记录那几个字母的值，然后在s中遍历，如果某一段长度为a，那么子串数就是 (a*(a+1)/2)就OK了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main()
{
	int n, k; cin >> n >> k;
	char s[N]; cin >> s;
	for (int i = 'a'; i <= 'z'; i++)
		a[i] = 0;
	for (int i = 0; i<k; i++)
	{
		char t; cin >> t;
		a[t]=1;
	}
	ll sum = 0, y = 0;
	for (int i = 0; i<strlen(s); i++)
	{
		if (a[s[i]]!=0)
		{
			y++;
		}
		else
		{
			sum = sum + (y * (y + 1) / 2); y =0;
		}
	    
	}
	if(y!=0)
		sum = sum + (y * (y + 1) / 2);
	cout << sum << endl;
}

☀☀☀☀☀☀☀☀☀☀

题意：在某个区间内如果连续k次出现了某个数的倍数，而另一个数在这个区间内没出现，那么输出 “REBEL” 否则输出“OBEY”
思路：先把两个数化简（除以公因数）如果两个数相等就一定可以obey，不相等就一定有一个大数和一个小数，连续的k个数一定就是那个小数，那么判定条件就出来了，在两个b之间是否可以有k个r 即（k-1）*r+1 < b -1

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b, a % b);
}
int main()
{int t;
    cin>>t;
    while(t--)
    {
        ll r,b,k;
        cin>>r>>b>>k;
        if(r>b)
            swap(r,b);
        ll g=gcd(r,b);
        r/=g,b/=g;
        if(r==b)
        {
            cout<<"OBEY"<<endl;
        }
        else if(b-1<(k-1)*r+1)
            cout<<"OBEY"<<endl;
        else
            cout<<"REBEL"<<endl;
    }
}

题意：输入 n,m,d;n就是河岸之间的距离，m是你几个不同长度的石头，d是你能跳的距离就是你能在i最多跳到i+d的地方，问你能不能过桥，并输出河岸间点的情况，如果铺了石头，输出那个石头编号，没铺石头，就输出0；
思路：先判断能不能到达对岸，就是算你能走的距离是多少，首先石头就有距离，把石头距离s=a[i]的和，还有你每个石头都能跳，这个时候需要注意两点你跳过的距离应该再算就是d-1了因为你石头距离已经算了，其次你在起点的时候你就开始跳了，所以石头的数量是m+1。所以距离是 (m + 1) * (d - 1)+s；
然后你设个标志代表自己到了那里了，然后你在进行跳，你需要设个变量考虑剩余的距离，以免到最后跳过头了！你跳的时候
tiao=min(sh,d-1)；然后找个b数组来储存那个每个点上的数字就行了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[1000002];
ll b[1000002];
int main()
{
    
       ll n, m, d;
        cin >> n >> m >> d;
       ll s = 0;
        for (ll i = 1; i <=m; i++)
        {
            cin >> a[i]; s += a[i];
        }
        if ((m + 1) * (d - 1) < n - s)
        {
            cout << "NO" << endl;
        }
        else
        {
            cout << "YES" << endl;
            ll num = 1;
           ll sh = n - s;
            for (ll z = 0; z<n;)
            {
              ll tiao;
                if (sh < d - 1)

                    tiao = sh;
                else
                    tiao = d - 1;
                for (ll i = 1; i <= tiao; i++)
                {
                    b[z] = 0; z++;
                }
                while (a[num])
                {
                    b[z] = num;
                    a[num]--;
                    z++;
                }
                num++;
                sh -= tiao;
            }
            for (ll i = 0; i < n; i++)
                cout << b[i] << " ";
            cout << endl;
        }
    
}

D - D CodeForces - 1249C2

题意：找一个比n大的数字，这个数字能可以被3的幂的和来表示，但是 3的幂不能重复。
思路：若xi没有重复，则反复令n/=3,每次n%3得到的都应该是0或者1。反之，若n不是好数，则在n/=3的过程中，一定会出现n%3=2的情况，籍此可以作为判断依据。当求余为2 代表着重复了！！！！！！！！！！！！！！！！！！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
	int t; cin >> t;
	while (t--)
	{
		int n; cin >> n;
		while (1)
		{
			int f = 1, m = n;
			while (m)
			{
				if (f && m % 3 == 2)
					f = 0;
				m = m / 3;
			}
			if (f) break;
			n++;
		}
		cout << n << endl;	
	}
}

E - E CodeForces - 1249B2

记住：在一个循环圈里的人都一样就可以了找queue来记录，然后把每个人都赋值上就可以了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
ll  a[300000], b[300000];
int main()
{ll  t; cin >> t;
	while (t--)
	{
		ll n; cin >> n;
		memset(b, 0, sizeof b); memset(a, 0, sizeof a);
		for (ll i = 1; i <= n; i++)
			cin >> a[i];
		queue<int>c;
		for (ll i = 1; i <= n; i++)
		{
			if (b[i] != 0) continue;
			else
			{
				ll m = i;
				c.push(m);
				m = a[m];
				while (m != i)
				{
					c.push(m); m = a[m];
				}
				ll s = c.size();
				while (!c.empty())
				{
					b[c.front()] = s;
					c.pop();
				}
			}
		}
		for (int i = 1; i <= n; i++)
			cout << b[i] << " ";cout << endl;
	}
}

F - F CodeForces - 1249D1

题意：有几条线段，如果某个点被k个线段覆盖，这个点就是坏点，然后你需要删除尽可能少的线段，来达到没有坏点，输出删除的线段顺序！
思路：建立vector< tybef >v[N]，然后在输入线段数据的时候把线段的左区间当做下标，而把左右区间赋值给它。
然后我找了个maxx记录最大的left区间，从1–maxx 挨着看，当遍历到i的时候，先把左区间为i的放到s里面，然后判断i点 s.size()与k之间的关系，如果大于k，这个点是坏的，然后把下标为i的 s的id值给ans里面放着，然后再去继续遍历

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int n, k;
struct Node
{
	int y;
	int idx;
};
bool operator<(Node a, Node b)//排序
{
	if (a.y != b.y)
		return a.y < b.y;
	return a.idx < b.idx;
}
vector<Node> g[N];
vector<int> ans;
int main()
{
	int x, y;
	cin >> n >> k;
	int maxx = 0;
	for (int i = 1; i <= n; i++)
	{
		Node p;
		cin >> x >> y;//left right
		p.y = y;
		maxx = max(maxx, x);
		p.idx = i;
		g[x].push_back(p);//left为下标 
	}
	set<Node> s;
	for (int i = 1; i <=maxx; i++)
	{     
		while (s.size() && (*s.begin()).y < i)//没有被覆盖的区间删除
			s.erase(*s.begin());
		for (int j = 0; j < g[i].size(); j++)//存入可覆盖区间
			s.insert(g[i][j]);
		while (s.size() > k)//判断该点被覆盖次数是否超过 k
		{
			ans.push_back((*s.rbegin()).idx);//删除的区间存下,直接存入最后一个元素！
			s.erase(*s.rbegin());
		}
	}
	cout << ans.size() << endl;
	int len = ans.size();
	for (int i = 0; i < len; i++)
	{
		cout << ans[i] << ' ';
	}cout << endl;
	
}

G - G CodeForces - 1251E1

题意：你要别人投票，每个人有 mi，pi，分别代表如果有mi个人都投票给你了，那这个人就免费给你投票，否则你得花pi钱来收买他！问你最少花多少钱能让所有人都投票给你。
思路：要注意到mi是小于n的。我们可以先建个vector容器v，然后用mi为下标push_back(pi)；因为这个可能会有重复的所以在建立 vector是建立这样的 vectorv[N]；然后建立那个优先队列的（小的数在前面的），然后我们从后往前看（先贿赂大的mi 啊！），然后每次i 都停下来判断当mi==i 时的人数是不是>n-i 是的话说明不能免费啊，得再去贿赂一个人。就这样来思考的
代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
vector <ll> v[N];
priority_queue<ll, vector<ll>, greater<ll>>q;
int main()
{     
	int t; cin >> t;
	while (t--)
	{
		int x, y, n; cin >> n;
		for (int i = 0; i <= n; i++)
			v[i].clear();
		while (!q.empty())
			q.pop();
		for (int i = 0; i < n; i++)
		{
			cin >> x >> y;//输入 mi和pi
			v[x].push_back(y);
		}
		ll s = 0;
		for (int i=n-1; i >= 0; i--)
		{
			ll len = v[i].size();
			for (int j = 0; j < len; j++)
				q.push(v[i][j]);
			while (q.size()>n-i)
			{
				s += q.top();
				q.pop();
			}
		}
		cout << s << endl;
	}

}