【AtCoder】ARC085
2024-08-26 05:22:51
C - HSI
题解
\(E = 1900 * (N - M) + 100 * M + \frac{1}{2^{M}} E\)
\(E = 2^{M}(1900 * (N - M) + 100 * M)\)
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M;
void Solve() {
read(N);read(M);
int ans = M * 1900 + (N - M) * 100;
for(int i = 1 ; i <= M ; ++i) ans *= 2;
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
D - ABS
简单的minmax搜索，就是dp[i][0/1]表示前一张牌是第i张，0是X局面，1是Y局面
每次在X层取max，在Y层取min
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 2005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,Z,W;
int a[MAXN],dp[MAXN][2];
int dfs(int on,int t) {
if(dp[t][on] != -1) return dp[t][on];
dp[t][on] = abs(a[t] - a[N]);
for(int i = 1 ; i < N - t ; ++i) {
if(on == 0) dp[t][on] = max(dp[t][on],dfs(on ^ 1,t + i));
else dp[t][on] = min(dp[t][on],dfs(on ^ 1,t + i));
}
return dp[t][on];
}
void Solve() {
read(N);read(Z);read(W);
a[0] = W;
for(int i = 1 ; i <= N ; ++i) read(a[i]);
memset(dp,-1,sizeof(dp));
out(dfs(0,0));
enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
E - MUL
题解
相当于把边权取反后求一个最大权闭合子图
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 105
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
struct node {
int to,next;
int64 cap;
}E[MAXN * MAXN * 2];
int sumE = 1,head[MAXN],S,T;
int64 a[MAXN];
void add(int u,int v,int64 c) {
E[++sumE].to = v;
E[sumE].next = head[u];
E[sumE].cap = c;
head[u] = sumE;
}
void addtwo(int u,int v,int64 c) {
add(u,v,c);add(v,u,0);
}
int gap[MAXN],dis[MAXN],last[MAXN];
int64 sap(int u,int64 aug) {
if(u == T) return aug;
int64 flow = 0;
for(int i = last[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(E[i].cap > 0) {
if(dis[v] + 1 == dis[u]) {
int64 t = sap(v,min(E[i].cap,aug - flow));
E[i].cap -= t;E[i ^ 1].cap += t;
flow += t;
if(flow == aug) return flow;
if(dis[S] >= T) return flow;
}
}
}
if(--gap[dis[u]++] == 0) dis[S] = T;
++gap[dis[u]];
last[u] = head[u];
return flow;
}
void Solve() {
read(N);
int64 ans = 0,tmp = 0;
for(int i = 1 ; i <= N ; ++i) {
read(a[i]);
ans += a[i];
}
S = N + 1,T = N + 2;
for(int i = 1 ; i <= N ; ++i) {
if(a[i] > 0) addtwo(i,T,a[i]);
else if(a[i] < 0) {
addtwo(S,i,-a[i]);
tmp -= a[i];
}
}
for(int i = 1 ; i <= N ; ++i) {
int t = 2 * i;
while(t <= N) {
addtwo(i,t,2e9);
t += i;
}
}
for(int i = 1 ; i <= N + 2 ; ++i) last[i] = head[i];
while(dis[S] < T) tmp -= sap(S,1e18);
ans += tmp;
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
F - NRE
题解
本来想着外国人真是瞧不起中国的数据结构水平啊看我用数据结构艹过去这题
结果题解就是数据结构= =
就是把区间按右端点排序，然后每次扫到一个右端点用左端点取更新它
同时把这个区间的左端点\(dp[l - 1] - (l - 1) + sum[l - 1]\)的值更新给\([l,r]\)
一个点的dp值认为是在不断的dp时的dp值，还有是线段树里的最小值加上这个点的\(r - sum[r]\)
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,Q;
int dp[MAXN],b[MAXN];
int sum[MAXN],cnt[MAXN];
vector<int> ed[MAXN];
struct node {
int l,r,cov;
}tr[MAXN * 4];
void build(int u,int l,int r) {
tr[u].l = l;tr[u].r = r;tr[u].cov = 2 * N;
if(l == r) return;
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
}
void Change(int u,int l,int r,int v) {
if(tr[u].l == l && tr[u].r == r) {
tr[u].cov = min(tr[u].cov,v);
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) Change(u << 1,l,r,v);
else if(l > mid) Change(u << 1 | 1,l,r,v);
else {Change(u << 1,l,mid,v);Change(u << 1 | 1,mid + 1,r,v);}
}
int Query(int u,int pos,int v) {
if(tr[u].l == tr[u].r) {
v = min(v,tr[u].cov);
return v + tr[u].l - sum[tr[u].l];
}
int mid = (tr[u].l + tr[u].r) >> 1;
if(pos <= mid) return Query(u << 1,pos,min(v,tr[u].cov));
else return Query(u << 1 | 1,pos,min(v,tr[u].cov));
}
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) {
read(b[i]);
sum[i] = sum[i - 1] + b[i];
}
read(Q);
int l,r;
build(1,0,N);
for(int i = 1 ; i <= Q ; ++i) {
read(l);read(r);
ed[r].pb(l);
}
dp[0] = 0;
for(int i = 1 ; i <= N ; ++i) {
dp[i] = i;
if(b[i] == 0) dp[i] = min(dp[i - 1],dp[i]);
else dp[i] = min(dp[i - 1] + 1,dp[i]);
for(auto t : ed[i]) {
dp[i] = min(min(Query(1,t - 1,2 * N),dp[t - 1]) + (i - t + 1) - (sum[i] - sum[t - 1]),dp[i]);
}
for(auto t : ed[i]) {
int a = min(Query(1,t - 1,2 * N),dp[t - 1]);
Change(1,t,i,a - (t - 1) + sum[t - 1]);
}
}
out(dp[N]);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
最新文章
- 12 自定义标签/JSTL标签库/web国际化/java web之设计模式和案例
- Chrome 自动填充的表单是淡黄色的背景，有方法自定义吗
- 【java基础】重载与重写
- JavaScript事件大全
- 使用windows服务和MSMQ和进行日志管理（解决高并发问题）
- ArcGIS Engine栅格数据使用总结
- EassyUI内置方法与属性
- 【转】使用 NuGet 管理项目库-Phil Haack
- linux配置备忘
- linux 之 snprintf函数用法
- TFS 测试用例导入、导出工具
- 基于jdk1.8的ArrayList源码分析
- Arch Linux安装Firefox 火狐中文版
- Delphi 中的 IfThen 函数
- [tomcat启动报错]registered the JDBC driver [com.alibaba.druid.proxy.DruidDriver] but failed to unregister it when the web application was stopped
- Java：集合，Collections工具类用法
- 小tip: 如何让contenteditable元素只能输入纯文本
- git clone时提示(gnome-ssh-askpass:29288): Gtk-WARNING **: cannot open display:
- Windows环境下 PyQt5 如何安装MySql驱动 （PyQt5连接MYSQL时显示Driver not loaded解决方案）
- hdu 5505(数论-gcd的应用)