LiM_233

2210

1lgorithm

lyktes
Alexshwing

RainSure
008

LiM_233
2020-05-02 13:37

Day 1 初赛

Day 2 小组赛

good luck.

Day 4

LiM_233
2020-02-01 12:05
#include <bits/stdc++.h>
using namespace std;

int a[7], l[1000], cnt;
bool dp[120000];
int main() {
while (1) {
cnt = 0;
memset(dp, 0, sizeof(dp));
int sum = 0;
for (int i = 1; i <= 6; ++i) cin >> a[i], sum += a[i] * i;
if (count (a + 1, a + 7, 0) == 6) return 0;
for (int i = 1; i <= 6; ++i) {
int pr = 1;
while (a[i] >= pr) a[i] -= pr, l[++cnt] = pr * i, pr *= 2;
if (a[i]) l[++cnt] = a[i] * i;
}
dp[0] = 1;
for (int i = 1; i <= cnt; i++)
for (int j = sum; j >= 1; j--)
dp[j] |= dp[j - l[i]];
puts((sum % 2 == 0 && dp[sum / 2]) ? "Can": "Can't");
}
return 0;
}


LiM_233
2020-02-01 11:59
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

#pragma GCC optimize(2)
#pragma GCC optimize(3)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

inline int gi() {
int f = 1, x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -f; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - 48; ch = getchar(); }
return f == 1 ? x : -x;
}

const int N = 1111111;
int n, a, b, c, x[N], l = 1, r = 0;
ll s[N], g[N], dp[N];
struct node {
ll X, Y;
int id;
node (ll X=0, ll Y=0, int id=0): X(X), Y(Y), id(id){}
}q[N];
double slope(node x, node y) {
return (double)(y.Y - x.Y) / (double)(y.X - x.X);
}
int main() {
n = gi(), a = gi(), b = gi(), c = gi();
rep (i, 1, n) x[i] = gi(), s[i] = s[i - 1] + x[i];
rep (i, 1, n) g[i] = a * s[i] * s[i] + b * s[i] + c;
dp[0] = 0;
q[++r] = node(0, 0, 0);
rep (i, 1, n) {
const double S = 2 * a * s[i];
while (l < r && slope(q[l], q[l + 1]) > S) ++l;
int j = q[l].id;
dp[i] = dp[j] + a * s[j] * s[j] - 2 * a * s[i] * s[j] - b * s[j] + g[i];
ll gg = dp[i] + a * s[i] * s[i] - b * s[i];
node t(s[i], gg, i);
while (l < r && slope(q[r - 1], q[r]) < slope(q[r], t)) --r;
q[++r] = t;
}
cout << dp[n] << endl;
return 0;
}


LiM_233
2020-02-01 11:57
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <vector>

using namespace std;

const int MAXN = 12 + 10;
const int TOTAL = (1 << 12) + 10;
const int MOD = 1000000000;
int n , m , a[MAXN] , state[TOTAL] , dp[MAXN][TOTAL];
// 1 & 1 = 1
//0 & 0 = 1

int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
int total = 0;
for(int j = 1;j <= m;j++){
int t;
cin >> t;
total = (total << 1) + t;
}
a[i] = total;
}

//for(int i = 1;i <= n;i++) cout << a[i] <<endl;
int MAX_STATE = (1 << m);
for(int i = 0;i < MAX_STATE;i++){
if(((i) & (i << 1)) == 0 && ((i) & (i >> 1)) == 0) state[i] = true;
}

dp[0][0] = 1;

for(int i = 1;i <= n;i++){
for(int j = 0;j < MAX_STATE;j++){
//printf("DEBUG1\n");
if(state[j] && ((j) & (a[i])) == j){
//printf("DEBUG2\n");
for(int k = 0;k < MAX_STATE;k++){
if(!((j) & (k))){
//printf("%d %d\n" , dp[i][j] , dp[i - 1][k]);
dp[i][j] += dp[i - 1][k];
dp[i][j] %= MOD;
}
}
}
}
}

int tot = 0;
for(int i = 0;i < MAX_STATE;i++) tot += dp[n][i] , tot %= MOD;
cout << tot;
return 0;
}


LiM_233
2020-02-01 11:56
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 100 + 10
using namespace std;

int a[MAXN << 1] , dp[MAXN << 1][MAXN << 1];
int N;
int maxn = 0;

int DP(int l , int r){
//cout << i << " " << j << endl;
int &sum = dp[l][r];
if(l == r - 1)return sum = a[l] * a[r] * a[r + 1];
if(sum) return sum;
for(int k = l;k < r;k++){
sum = max(sum , DP(l , k) + DP(k + 1 , r) + a[l] * a[k + 1] * a[r + 1]);
}
return sum;
}
int main()
{
cin >> N;
for(int i = 1;i <= N;i++){
cin >> a[i];
a[N + i] = a[i];
}
a[2 * N + 1] = a[1];
for(int i = 1;i <= N;i++){
//memset(dp , 0 , sizeof(dp));
maxn = max(maxn , DP(i , N + i - 1));
}
cout << maxn;
return 0;
}



LiM_233
2020-02-01 11:40
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}
int dp[1000][1000], lsts[1000][26], lstt[1000][26];
string s, t;
vector <char> v;
vector <vector <char> > vv;
map<vector<char>, int> mp;
void track(int i, int j, int now) {
if (!dp[i][j]) {
if (!mp[v]) {
mp[v] = 1;
vector<char> v1 = v;
reverse(v1.begin(), v1.end());
vv.push_back(v1);
}
return;
}
for (int ch = 0; ch < 26; ++ch) {
int pi = lsts[i][ch], pj = lstt[j][ch];
if (dp[pi][pj] == now) {
v.push_back(ch + 'a');
track(pi - 1, pj - 1, now - 1);
v.pop_back();
}
}
}
int main() {
cin >> s >> t;
int n = s.size(), m = t.size();
s = " " + s;
t = " " + t;
rep (i, 1, n) {
memcpy(lsts[i], lsts[i - 1], sizeof(lsts[i - 1]));
lsts[i][s[i] - 'a'] = i;
}
rep (i, 1, m) {
memcpy(lstt[i], lstt[i - 1], sizeof(lstt[i - 1]));
lstt[i][t[i] - 'a'] = i;
}
int ans = 0;
rep (i, 1, n) {
rep (j, 1, m) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (s[i] == t[j])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
ans = max(ans, dp[i][j]);
}
}
track(n, m, ans);
sort(vv.begin(), vv.end());
for (auto e: vv) {
for (auto ch: e)
cout << ch;
puts("");
}
return 0;
}


LiM_233
2020-01-29 13:33
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}

const int N = 5005;
int n, a[N], f[N], num[N];
int main() {
n = gi();
rep(i, 1, n) a[i] = gi();

rep (i, 1, n) {
f[i] = 1;
rep (j, 1, i-1)
if (a[j] > a[i]) f[i] = max(f[i], f[j] + 1);
}

rep (i, 1, n) {
if (f[i] == 1)
num[i] = 1;
rep (j, 1, i-1) {
if (a[j] > a[i] && f[j] + 1 == f[i])
num[i] += num[j];
else if (a[j] == a[i] && f[j] == f[i])
num[i] = 0;
}
}
int ANS = *max_element(f + 1, f + n + 1), ans = 0;
rep (i, 1, n) if (f[i] == ANS) ans += num[i];
cout << ANS << " " << ans << endl;
return 0;
}


LiM_233
2020-01-29 13:17
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}

const int N = 105;
int f, v, val[N][N], dp[N][N], prv[N][N];
int calc(int i, int j) {
if (i < j)
return -0x3f3f3f3f;
if (dp[i][j] != -1)
return dp[i][j];
if (j == 0)
return dp[i][j] = 0;

if (calc(i - 1, j) >= calc(i - 1, j - 1) + val[j][i])
dp[i][j] = calc(i - 1, j), prv[i][j] = j;
else
dp[i][j] = calc(i - 1, j - 1) + val[j][i], prv[i][j] = j - 1;
return dp[i][j];
}
int main() {
memset(dp, -1, sizeof(dp));
f = gi(), v = gi();
rep(i, 1, f) rep(j, 1, v) val[i][j] = gi();
cout << calc(v, f) << endl;

int nowx = v, nowy = f;
vi v;
while (nowx) {
if (prv[nowx][nowy] != nowy)
v.push_back(nowx);
nowy = prv[nowx][nowy];
--nowx;
}
reverse(v.begin(), v.end());
for (int i = 0; i < v.size(); ++i)
cout << v[i] << " ";
return 0;
}


LiM_233
2020-01-29 13:07
#include <bits/stdc++.h>
#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}

int dp[45][45][45][45], cnt[5], A[355], n, m;

int f(int a, int b, int c, int d) {
if (dp[a][b][c][d] != -1) return dp[a][b][c][d];
if (!(a|b|c|d))
return dp[a][b][c][d] = A[1];
int res = 0;
if(a >= 1) res = max(res, f(a-1, b, c, d));
if(b >= 1) res = max(res, f(a, b-1, c, d));
if(c >= 1) res = max(res, f(a, b, c-1, d));
if(d >= 1) res = max(res, f(a, b, c, d-1));
return dp[a][b][c][d] = res + A[1 + a + 2 * b + 3 * c + 4 * d];
}
int main() {
memset(dp, -1, sizeof(dp));
n = gi(), m = gi();
rep(i, 1, n) A[i] = gi();
rep(i, 1, m)++ cnt[gi()];
cout << f(cnt[1], cnt[2], cnt[3], cnt[4]) << endl;
return 0;
}