鄭州軽工業大学「CCPC 2019-ハナム省戦」選抜試合(2)の部分は問題を解きます.

59868 ワード

_。ダイナミック企画_ _。データ構造_ _。数学数論_ 欲が深い 2分3分暴力列挙区間dp 組み合わせの数単調なスタック

テーマリンク
Aマッチ棒等式

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
 
int x[] =
{
0
,0
,0
,0
,0
,0
,0
,0
,0
,0
,0
,0
,0
,1
,2
,8
,9
,6
,9
,29
,39
,38
,65
,88
,128
,194
,323
,472
,656
};
 
int main()
{
#ifdef LOCAL
    //freopen("C:/input.txt", "r", stdin);
#endif
    int y;
    while (scanf("%d", &y) != EOF)
        printf("%d
", x[y]);
 
    return 0;
}

Cセット

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
 
int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}
int main()
{
#ifdef LOCAL
    //freopen("C:/input.txt", "r", stdin);
#endif
    int n, p;
    cin >> n >> p;
    int g = p;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        scanf("%d", &x);
        g = gcd(g, x);
    }
    cout << p / g <<endl;
 
    return 0;
}

E小Lの加算器

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
 
int main()
{
#ifdef LOCAL
    //freopen("C:/input.txt", "r", stdin);
#endif
    int n;
    cin >> n;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for (int i = 0; i < n; ++i)
    {
        ll x;
        scanf("%lld", &x);
        pq.push(x);
    }
    ll ans = 0;
    while (--n)
    {
        ll a = pq.top();
        pq.pop();
        ll b = pq.top();
        pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    cout <<ans << endl;
 
    return 0;
}

F毎日のピアノ

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
ll fac[N], inv[N];
ll a[N];
 
ll mpow(ll a, ll b, ll c)
{
    ll t = 1;
    while (b)
    {
        if (b & 1)
            t = t * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return t;
}
ll C(int n, int m)
{
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main()
{
#ifdef LOCAL
    freopen("C:/input.txt", "r", stdin);
#endif
    fac[0] = inv[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = mpow(fac[i], MOD - 2, MOD);
    }
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1, greater<int>());
    ll ans = 0;
    for (int i = 1; i <= n - k + 1; ++i)
        ans = (ans + a[i] * C(n - i, k - 1) % MOD) % MOD;
    cout << ans <<endl;
 
    return 0;
}

G小Lの試合パスワード

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
 
int main()
{
#ifdef LOCAL
    //freopen("C:/input.txt", "r", stdin);
#endif
    int x, y, z = 1, p;
    cin >> x >> y;
    while (cin >> p)
    {
        if (p > x || p < y)
            cout << z << endl, exit(0);
        z++;
    }
 
    return 0;
}

H黒い塊を踏むな

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e3 + 10;
char g[N][N];
int H[N]; //     

struct node
{
	int h, w; //    
};
int main()
{
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
	int n, m;
	while (cin >> n >> m)
	{
		memset(H, 0, sizeof(H));
		for (int i = 1; i <= n; ++i)
			scanf("%s", g[i] + 1);
		ll ans = 0;
		for (int i = 1; i <= n; ++i) //   
		{
			stack<node> stk; //            
			ll cnt = 0; //              
			for (int j = 1; j <= m; ++j) //   g[i][j]         
				if (g[i][j] == 'W')
				{
					H[j] = cnt = 0; //    
					while (!stk.empty())
						stk.pop();
				}
				else
				{
					++H[j]; //   +1
					node t = { H[j], 1 }; //         H[j]*1   
					while (!stk.empty() && stk.top().h >= t.h) //                  
					{
						t.w += stk.top().w; //      
						cnt -= 1LL * stk.top().w * stk.top().h; //                   
						stk.pop();
					}
					stk.push(t);
					cnt += 1LL * t.h * t.w; //      
					ans += cnt; //cnt                      
				}
		}
		cout << ans << endl;
	}

	return 0;
}

Iメンバー統計

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
 
int main()
{
#ifdef LOCAL
    freopen("C:/input.txt", "r", stdin);
#endif
    int n;
    cin >> n;
    map<int, int> mp;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        scanf("%d", &x);
        ++mp[x];
    }
    for (auto it : mp)
        printf("%d %d
", it.fst, it.sed);
 
    return 0;
}

Jさんの友達

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e4 + 10;
vector<int> e[N];
int f[N][2];
 
void DFS(int x, int fz)
{
    f[x][1] = 1;
    for (int y : e[x]) if (y != fz)
    {
        DFS(y, x);
        f[x][0] += max(f[y][0], f[y][1]);
        f[x][1] += f[y][0];
    }
}
int main()
{
#ifdef LOCAL
    freopen("C:/input.txt", "r", stdin);
#endif
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    DFS(1, 0);
    cout << max(f[1][0], f[1][1]) << endl;
 
    return 0;
}

Kさんはもちを分けます

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const long double pi = acos(-1);
int n, m;
vector<int> vec;
 
bool check(double ans)
{
    int cnt = 0;
    for (int i = 0; i < vec.size(); ++i)
    {
        double area = pi * vec[i] * vec[i];
        cnt += area / ans;
    }
    return cnt >= m;
}
int main()
{
#ifdef LOCAL
    //freopen("C:/input.txt", "r", stdin);
#endif
    cin >> n >> m;
    ++m;
    for (int i = 0; i < n; ++i)
    {
        int x;
        scanf("%d", &x);
        vec.push_back(x);
    }
    double l = 0, r = 1e18;
    while (abs(l - r) > 1e-6)
    {
        double m = (l + r) / 2;
        if (check(m))
            l = m;
        else
            r = m;
    }
    printf("%.3f
", l);
 
    return 0;
}

Asimp data structureの紹介