Codeforces Round #327 (Div. 2)

时间：2023-11-20 13:53:02

题目传送门

水 A - Wizards' Duel

题目都没看清就写了，1e-4精度WA了一次。。。

/************************************************

* Author        :Running_Time

* Created Time  :2015/10/25 16:27:20

* File Name     :A.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

int main(void)    {

	int L, p, q;

	scanf ("%d%d%d", &L, &p, &q);

	double ans = L * (p * 1.0) / (p + q);

	printf ("%.5f\n", ans);

    return 0;

}

构造 B - Rebranding

题意：要求字符串的所有C1字符变成C2，C2变成C1，输出最后的结果

分析：想了一会，试了并查集，未果，YY，未果。最后想了一个很奇怪的方法，就是每次记录C1的最原始的字符rt[C1]，它将转换为C2，即to[rt[C1]] = C2

/************************************************

* Author        :Running_Time

* Created Time  :2015/10/25 16:27:20

* File Name     :B.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 2e6 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

char s[N];

int to[30], rt[30];

int main(void)    {

	int n, m;	scanf ("%d%d", &n, &m);	getchar ();

	scanf ("%s", &s);	getchar ();

	char c1, c2;

	memset (to, -1, sizeof (to));

	for (int i=0; i<26; ++i)	rt[i] = i;

	for (int i=1; i<=m; ++i)	{

		scanf ("%c %c", &c1, &c2);	getchar ();

		int tmp = rt[c2-'a'];

        to[rt[c1-'a']] = c2 - 'a';

        to[rt[c2-'a']] = c1 - 'a';

        rt[c2-'a'] = rt[c1-'a'];

        rt[c1-'a'] = tmp;

	}

	for (int i=0; i<n; ++i)	{

		if (to[s[i]-'a'] == -1)	printf ("%c", s[i]);

		else	printf ("%c", 'a' + to[s[i]-'a']);

	}

	puts ("");

    return 0;

}

　　

找规律 C - Median Smoothing

题意：由01构成的序列，每一次a[i] = (a[i-1], a[i], a[i+1])的第二大，问多少次序列会稳定

分析：列出(a[i-1], a[i], a[i+1])的所有组合，发现只有010和101是不稳定的，所以找出这样的连续的最长的串，操作次数就是max_len / 2

/************************************************

* Author        :Running_Time

* Created Time  :2015/10/25 16:27:20

* File Name     :C.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 5e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

int a[N];

int main(void)    {

	int n;	scanf ("%d", &n);

	for (int i=1; i<=n; ++i)	{

		scanf ("%d", &a[i]);

	}

    int ans = 0;

    for (int i=2; i<n; ++i)   {

        if (a[i] != a[i-1]) {

            int j = i;

            while (j < n && a[j] != a[j+1] && a[j] != a[j-1])   j++;

            ans = max (ans, (j - i + 1) >> 1);

            int p = i, q = j - 1;

            while (p <= q)  {

                a[p++] = a[i-1];

                a[q--] = a[j];

            }

            i = j;

        }

    }

    printf ("%d\n", ans);

    for (int i=1; i<=n; ++i)    {

        printf ("%d%c", a[i], i == n ? '\n' : ' ');

    }

    //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

　　

相关文章