A. Minimum Binary Number
显然可以把所有(1)合并成一个
注意没有(1)的情况
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
void solve(){
int n;
string s;
cin >> n >> s;
int c0 = 0, c1 = 0;
for(int x : s) if(x=='0') c0++; else c1++;
if(!c1) cout << 0 << endl;
else{
cout << 1;
while(c0--) cout << 0;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
B. Lara Croft and the New Game
就摁模拟它怎么走的就好了，有点小麻烦
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef long long int LL;
void solve(){
LL n, m, k;
cin >> n >> m >> k;
if(k<n) cout << k + 1 << ' ' << 1 << endl;
else{
k -= n;
int num = k / (m-2+m);
int lft = k % (m-2+m);
int x = n - 2 * num;
if(!lft) cout << x << ' ' << 2 << endl;
else{
if(lft<=m-2) cout << x << ' ' << 2 + lft << endl;
else{
lft -= m - 1;
x -= 1;
cout << x << ' ' << m - lft << endl;
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
C. Nested Segments
把所有线段先按左端点从小到大排序，左端点相同的按右端点从大到小排，然后扫一遍，这样就不用管左端点的大小关系了，只要维护遍历过程中右端点最右的位置和相应线段的编号即可
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 3e5+7;
int n;
pair<pair<int,int>,int> seg[MAXN];
void solve(){
____();
cin >> n;
for(int i = 1; i <= n; i++){
cin >> seg[i].first.first >> seg[i].first.second;
seg[i].second = i;
}
sort(seg+1,seg+1+n,[&](pair<pair<int,int>, int> a, pair<pair<int,int>,int > b){
if(a.first.first==b.first.first) return a.first.second > b.first.second;
else return a.first.first < b.first.first;
});
int rm = 0, id = 0;
for(int i = 1; i <= n; i++){
if(seg[i].first.second>rm){
rm = seg[i].first.second;
id = seg[i].second;
}else{
cout << seg[i].second << ' ' << id << endl;
return;
}
}
cout << -1 << ' ' << -1 << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
D. Degree Set
一开始有(d_n+1)个点，要构造出度数集合为(d_1,d_2,cdots,d_n)的图
把编号(1-d_1)的点向其他所有点连边，那么(1-d_1)的点的度数为(d_n-1)，其他点的度数为(d_1)
保留(1-d_1)的点和(d_{n-1}+2-d_n+1)的点
剩下的(d_1+1-d_{n-1}+1)的点（一共(d_{n-1}-d_1+1)个点），需要构造一个度数集合为(d_2-d_1,d_3-d_1,cdots,d_{n-1}-d_1)的图，可以发现是一个小规模的原问题，递归解决即可
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e3+7;
void solve(){
____();
static int n, d[MAXN]; cin >> n;
for(int i = 1; i <= n; i++) cin >> d[i];
vector<pair<int,int> > edges;
int l = 1, r = n, D = 0;
for(int l = 1, r = n, D = 0; l <= r; D += d[l], l++, r--){
for(int i = 1; i <= d[l]; i++) for(int j = i + 1; j <= d[r] + 1; j++) edges.push_back({i+D,j+D});
for(int i = l + 1; i <= r - 1; i++) d[i] -= d[l];
}
printf("%d
",edges.size());
for(auto &e : edges) printf("%d %d
",e.first,e.second);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
E. Well played!
显然把生命翻倍给同一个随从是最优的
那么枚举给的这个随从即可
注意没有心火(攻击等于生命)的情况
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef long long int LL;
const int MAXN = 2e5+7;
int n, a, b;
pair<LL,LL> cre[MAXN];
LL pre[MAXN];
void solve(){
____();
cin >> n >> a >> b;
b = min(n,b);
for(int i = 1; i <= n; i++) cin >> cre[i].first >> cre[i].second;
sort(cre+1,cre+1+n,[&](pair<LL,LL> &a, pair<LL,LL> &b){
return a.first - a.second > b.first - b.second;
});
for(int i = 1; i <= n; i++) pre[i] = pre[i-1] + max(0ll,cre[i].first - cre[i].second);
LL sum = 0, ret = 0;
for(int i = 1; i <= n; i++) sum += cre[i].second;
ret = sum + pre[b];
sum += pre[b];
for(int i = 1; i <= b; i++){
LL ts = sum - max(0ll,cre[i].first-cre[i].second);
ts -= cre[i].second;
ret = max(ret,ts+(cre[i].first<<a));
}
if(b){
for(int i = b + 1; i <= n; i++){
LL ts = sum - max(0ll,cre[b].first-cre[b].second);
ts -= cre[i].second;
ret = max(ret,ts+(cre[i].first<<a));
}
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
F. Minimal k-covering
考虑网络流建图，所有边从左半图连右半图，容量为(1)，源点向左半图所有点连边，容量为(deg[x]-k)，右半图的点向汇点连边，容量为(deg[y]-k)，然后有流量的边边即为需要删掉的边
从大到小枚举(k)，每次从源点到左半图的点增加(1)容量的边，右半图的点向汇点增加(1)容量的边，增广一次即可
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 4e3+7;
const int INF = 0x3f3f3f3f;
#define S 0
#define T MAXN - 1
set<int> edges;
struct EDGE{
int to,cap,rev,id;
EDGE(){};
EDGE(int to, int cap, int rev, int id):to(to),cap(cap),rev(rev),id(id){};
};
vector<EDGE> G[MAXN];
int iter[MAXN],rk[MAXN];
void ADDEDGE(int u, int v, int cap, int id){
G[u].push_back(EDGE(v,cap,(int)G[v].size(),id));
G[v].push_back(EDGE(u,0,(int)G[u].size()-1,-id));
}
bool bfs(){
memset(rk,0,sizeof(rk));
memset(iter,0,sizeof(iter));
rk[S] = 1;
queue<int> que;
que.push(S);
while(!que.empty()){
int u = que.front();
que.pop();
for(auto e : G[u]){
if(!e.cap or rk[e.to]) continue;
rk[e.to] = rk[u] + 1;
que.push(e.to);
}
}
return rk[T]!=0;
}
int dfs(int u, int flow){
if(u==T) return flow;
for(int &i = iter[u]; i < (int)G[u].size(); i++){
auto &e = G[u][i];
if(!e.cap or rk[e.to]!=rk[u]+1) continue;
int d = dfs(e.to,min(e.cap,flow));
if(d){
e.cap -= d;
G[e.to][e.rev].cap += d;
if(e.id){
if(e.id>0) edges.erase(e.id);
else edges.insert(-e.id);
}
return d;
}
}
return 0;
}
void Dinic(){
while(bfs()){
int d = dfs(S,INF);
while(d) d = dfs(S,INF);
}
}
int n1, n2, m, deg1[MAXN], deg2[MAXN];
void solve(){
____();
cin >> n1 >> n2 >> m;
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
ADDEDGE(u,v+n1,1,i);
deg1[u]++; deg2[v]++;
}
for(int i = 1; i <= m; i++) edges.insert(i);
int mindeg = min(*min_element(deg1+1,deg1+1+n1),*min_element(deg2+1,deg2+1+n2));
vector<vector<int> > vec(mindeg,vector<int>());
for(int i = 1; i <= n1; i++) ADDEDGE(S,i,deg1[i]-mindeg,0);
for(int i = 1; i <= n2; i++) ADDEDGE(i+n1,T,deg2[i]-mindeg,0);
for(int k = mindeg; k; k--){
Dinic();
for(int e : edges) vec[k-1].push_back(e);
for(int i = 1; i <= n1; i++) ADDEDGE(S,i,1,0);
for(int i = 1; i <= n2; i++) ADDEDGE(i+n1,T,1,0);
}
puts("0");
for(int i = 0; i < mindeg; i++){
printf("%d",vec[i].size());
for(int x : vec[i]) printf(" %d",x);
puts("");
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}