题目来源：
Dashboard - 2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest - Codeforces
Dashboard - 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest - Codeforces
A. Auxiliary Project
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6 10;
int n;
int f[N];
int cost[10] = {
6, 2, 5, 5, 4, 5, 6, 3, 7, 6
};
/*
6 = 3 3 -> 7*2 = 14
7 = 3 4 -> 7 4 = 11
5 = 3 2 -> 7 1 = 8
4 = 4 -> 4
3 = 3 -> 7
2 = 2 -> 1
*/
void solve() {
cin >> n;
map<int, int> mp;
mp[6] = 14, mp[7] = 11, mp[5] = 8, mp[4] = 4;
mp[3] = 7, mp[2] = 1;
memset(f, 0xcf, sizeof f);
f[0] = 0;
for(auto it : mp) {
int v = it.fi, w = it.se;
for(int j = v; j <= n; j )
f[j] = max(f[j], f[j-v] w);
}
cout << f[n] << 'n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed; // << setprecision(20); // double
freopen("auxiliary.in", "r", stdin);
freopen("auxiliary.out ", "w", stdout);
// int Tcase;
// cin >> Tcase; // scanf("%d", &Tcase);
// while (Tcase--)
solve();
return 0;
}
/*
贪心好像也可以做，直接模3，然后稍微分类下就行
*/B. Consonant Fencity
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 26;
int cnt[N][N], refc[N];
void solve() {
string s;
cin >> s;
string dic = "bcdfghjklmnpqrstvxz";
memset(refc, -1, sizeof refc);
for(int i = 0; i < dic.size(); i ) {
char x = dic[i];
int p = x-'a';
refc[p] = i;
}
for(int i = 1; i < s.size(); i ) {
int a = refc[s[i-1]-'a'], b = refc[s[i]-'a'];
if(!~a || !~b) continue;
cnt[a][b] ;
cnt[b][a] ; // 两个互相相邻
}
int res = 0, rec = 0;
int T;
for(T = 0; T < (1<<19); T ) {
int tres = 0;
for(int i = 0; i < 19; i ) {
if(T>>i & 1) // upper
for(int j = 0; j < 19; j )
if((T>>j & 1) == 0) { // lower
tres = cnt[i][j];
}
}
if(tres > res) {
res = tres;
rec = T;
}
}
for(auto &x : s) {
int p = refc[x-'a'];
if(~p && (rec>>p & 1)) x = toupper(x);
}
cout << s << 'n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed; // << setprecision(20); // double
freopen("consonant.in", "r", stdin);
freopen("consonant.out", "w", stdout);
// int Tcase;
// cin >> Tcase; // scanf("%d", &Tcase);
// while (Tcase--)
solve();
return 0;
}
/*
没估计好复杂度 3秒限制，实际就枚举2^19次状态，每个check下它的pair数即可
一开始像确定前后关系来计cnt和tres，然后可以减少一般的枚举量，结果wa了
后面想到如果'z'为大写，小写和他相互结对的就不能记录个数了。
*/C. Intelligence in Perpendicularia
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
void solve() {
int n;
cin >> n;
vector<PII> a(n);
for(auto &x : a) cin >> x.fi >> x.se;
int xMx = a[0].fi, xMn = a[0].fi, yMx = a[0].se, yMn = a[0].se;
LL sum = 0;
for(int i = 1; i < n; i ) {
sum = abs(a[i].fi a[i].se-a[i-1].fi-a[i-1].se);
xMx = max(xMx, a[i].fi), xMn = min(xMn, a[i].fi);
yMx = max(yMx, a[i].se), yMn = min(yMn, a[i].se);
}
sum = abs(a[0].fi a[0].se-a[n-1].fi-a[n-1].se);
cout << sum-2*(xMx-xMn yMx-yMn) << 'n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed; // << setprecision(20); // double
freopen("intel.in", "r", stdin);
freopen("intel.out ", "w", stdout);
// int Tcase;
// cin >> Tcase; // scanf("%d", &Tcase);
// while (Tcase--)
solve();
return 0;
}
/*
不要被计算几何的外表骗了，实际只是脑经急转弯 —— dls
外面能看到的部分就是上下左右四个方向
就是x最大最小值、y最大最小值处理一下的值
*/D. Kotlin Island
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 110;
char g[N][N];
void solve() {
int n, m, k;
cin >> n >> m >> k;
int mx = (n 1)/2, my = (m 1)/2;
int x = -1, y = -1;
bool ok = false;
for(int i = 1; i <= mx; i ) {
for(int j = 1; j <= my; j )
if(i*j == k) {
x = i-1, y = j-1;
ok = true;
break;
}
if(ok) break;
}
if(!ok) {
cout << "Impossiblen";
return;
}
// cout << x << ' ' << y << 'n';
for(int i = 0; i < n; i )
for(int j = 0; j < m; j )
g[i][j] = '.';
for(int i = 1, j = 0; i < n && j < x; i = 2, j )
for(int u = 0; u < m; u )
g[i][u] = '#';
for(int i = 1, j = 0; i < m && j < y; i = 2, j )
for(int u = 0; u < n; u )
g[u][i] = '#';
for(int i = 0; i < n; i )
cout << g[i] << 'n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed; // << setprecision(20); // double
freopen("kotlin.in", "r", stdin);
freopen("kotlin.out", "w", stdout);
// int Tcase;
// cin >> Tcase; // scanf("%d", &Tcase);
// while (Tcase--)
solve();
return 0;
}E. Little Difference
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
bool is2(LL n) {
while(n % 2 == 0) n /= 2;
return n == 1;
}
void solve() {
LL n;
cin >> n;
vector<vector<LL>> ans;
if(n == 1 || is2(n)) {
cout << "-1n";
return;
}
else {
// cout << 1 << ' ' << n << 'n';
vector<LL> t(1, n);
ans.push_back(t);
}
LL t = (LL)(sqrt(n) 0.1);
if(n == t*(t 1)) {
// cout << 2 << ' ' << t << ' ' << t 1 << 'n';
vector<LL> tt(1, t);
tt.push_back(t 1);
ans.push_back(tt);
}
else if(n == t*t) {
// cout << 2 << ' ' << t << ' ' << t << 'n';
vector<LL> tt(2, t);
ans.push_back(tt);
}
for(LL i = 2; i*i*i <= n; i ) {
LL j = i 1, cnt0 = 0, cnt1 = 0;
if(n % i == 0) {
LL m = n;
while(m % i == 0) m /= i, cnt0 ;
if(m == 1) {
vector<LL> tt(cnt0, i);
ans.push_back(tt);
}
j = i 1, cnt0 = 0, cnt1 = 0;
if(n % (i*j) == 0) {
LL m = n;
while(m % i == 0) m /= i, cnt0 ;
while(m % j == 0) m /= j, cnt1 ;
if(m == 1) {
vector<LL> tt(cnt0, i);
for(int z = 0; z < cnt1; z )
tt.push_back(j);
ans.push_back(tt);
}
}
}
}
cout << ans.size() << 'n';
for(auto vec : ans) {
cout << vec.size();
for(auto x : vec)
cout << ' ' << x;
cout << 'n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed; // << setprecision(20); // double
freopen("little.in", "r", stdin);
freopen("little.out", "w", stdout);
// int Tcase;
// cin >> Tcase; // scanf("%d", &Tcase);
// while (Tcase--)
solve();
return 0;
}
/*
对题目理解不完全，只要是任意数最多差1，且不存在元素和数目相同就是一个合法方案
2^k都是无限种方案。
解法的话，看到数据范围，三次开方的复杂度可以接受，就1次和2次的另外处理即可。
*/F. Advertising Strategy
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
LL n, k;
LL Work(LL x) {
LL cnt = 1;
LL m = n-(k-x), last = -1;
while(x < m) {
// cout << x << 'n';
if(x == last) {
cnt = 1e18;
break;
}
last = x;
x = min(x, (n-x)/2);
cnt ;
}
return cnt;
}
void solve() {
cin >> n >> k;
LL res = 1e18;
for(int i = 1; i <= k; i ) {
res = min(res, Work(i));
}
cout << res << 'n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed; // << setprecision(20); // double
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
// int Tcase;
// cin >> Tcase; // scanf("%d", &Tcase);
// while (Tcase--)
solve();
return 0;
}
/*
增长的过程：
阶段一：
乘二
阶段二：
= (n-x)/2
所以是先快后慢，很容易得到中间时候放不如在开始或结尾放，所以枚举即可。
*/G. Carpet
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 10, M = 2e5 10;
int idx, h[N], ne[M], ver[M];
int son[N], siz[N];
int n, cnt[25];
PII p[N];
void add(int a, int b) {
ver[idx] = b, ne[idx] = h[a], h[a] = idx ;
}
void dfs1(int u, int fa) {
siz[u] = 1;
for(int i = h[u]; ~i; i = ne[i]) {
int v = ver[i];
if(v == fa) continue;
dfs1(v, u);
siz[u] = siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int fa, int line) {
p[u] = { cnt[line], line};
for(int i = h[u]; ~i; i = ne[i]) {
int v = ver[i];
if(v != fa && v != son[u])
dfs2(v, u, line 1);
}
if(son[u])
dfs2(son[u], u, line);
}
void solve() {
memset(h, -1, sizeof h);
cin >> n;
for(int i = 1; i < n; i ) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs1(1, -1);
dfs2(1, -1, 1);
for(int i = 1; i <= n; i )
cout << p[i].fi << ' ' << p[i].se << 'n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed; // << setprecision(20); // double
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
// int Tcase;
// cin >> Tcase; // scanf("%d", &Tcase);
// while (Tcase--)
solve();
return 0;
}
/*
轻重链剖分
先把轻儿子放在下一行，再把重儿子放在父节点这一行的右边
能够不挺分下去的儿子最多只有log n层，且列不会超出，符合
*/H. Decoding of Varints
代码语言：javascript复制#pragma GCC optimize(2)
#include <bits/stdc .h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
void solve() {
ULL n;
cin >> n;
ULL sum = 0, len = 1;
while(n --) {
ULL a;
cin >> a;
if(a >= 128) {
a -= 128;
sum = a*len;
len *= 128;
}
else {
sum = a*len;
if(sum & 1) {
cout << -(LL)(sum/2 1) << 'n'; // -(sum 1)/2
}
else {
cout << sum/2 << 'n';
}
sum = 0, len = 1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed; // << setprecision(20); // double
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
// int Tcase;
// cin >> Tcase; // scanf("%d", &Tcase);
// while (Tcase--)
solve();
return 0;
}
/*
题意在绕，读懂后按题意模拟即可
题目只保证被加密的数在LL范围，并不保证加密出来的数在LL范围
ps. 一开始我用了int128，然后后面发现加密出来的数最多超LL一倍，且是正数
所以也可以用ULL
*/
