- 1[记录]开发Hololens时Unity报错缺少UnityEngine.VR命名空间的问题
- 2Oracle分析SQL执行调优
- 3STM32 1-5
- 4unity3d 动态合批设置_Unity技术分享（82）|动态合批|渲染模块|animationclip.framerate...
- 5程序设计－从字符串中提取数字并按正序输出（Java）_java提取string中所有数字组合成新的
- 6常用的爆款抓包工具综合对比（选择最合适的抓包工具才是最重要的！）_抓包工具哪个好用
- 7【设计模式】适配器模式怎么理解？
- 8镜像的优化_powermill镜像项目里的优化是什么意思
- 9免费简单好用的 webshell 在线检测：支持 php、jsp、asp等多格式文件
- 10postman工具使用中，遇到的简单疑问_postman有缓存吗
Educational Codeforces Round 100 (Rated for Div. 2) CF1463A-F 题解_19.已知函数f的定义如下:| void f(int x0. inty) {inti; for(i=
赞
踩
A.
如果以
7
7
7为一个周期，可以知道我们可以打
9
9
9点伤害。所以要想完美过关，怪的生命值和一定是
9
9
9的倍数。同时我们可以算出需要
s
u
m
/
9
sum/9
sum/9个周期才能解决，因此每一个怪的生命值都要大于等于
s
u
m
/
9
sum/9
sum/9。
代码：
#include <iostream> #include <cstdio> using namespace std; int a,b,c,T; int main() { scanf("%d",&T); while (T--) { scanf("%d%d%d",&a,&b,&c); int sum=a+b+c; if ((sum%9==0) && (a>=sum/9) && (b>=sum/9) && (c>=sum/9)) printf("YES\n"); else printf("NO\n"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
B.
我们可以这样构造数列，
1
,
a
2
,
1
,
a
4
,
.
.
.
.
1,a_2,1,a_4,....
1,a2,1,a4,....
或者
a
1
,
1
,
a
3
,
1
,
.
.
.
.
a_1,1,a_3,1,....
a1,1,a3,1,....
显然这样的权值就是
a
1
−
1
+
a
3
−
1
+
.
.
.
a_1-1+a_3-1+...
a1−1+a3−1+...，或者
a
2
−
1
+
a
4
−
1
+
.
.
.
a_2-1+a_4-1+...
a2−1+a4−1+...
显然有一个权值小于
S
S
S的一半。
代码：
#include <iostream> #include <cstdio> #define LL long long const int maxn=107; using namespace std; int T,n; LL sum,l,r; LL a[maxn]; int main() { scanf("%d",&T); while (T--) { scanf("%d",&n); sum=l=r=0; for (int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum+=a[i]; } for (int i=1;i<=n;i++) { if (i&1) l+=a[i]; else r+=a[i]; } if (l<=sum/2) { for (int i=1;i<=n;i++) { if (i&1) printf("1 "); else printf("%lld ",a[i]); } } else { for (int i=1;i<=n;i++) { if (i&1) printf("%lld ",a[i]); else printf("1 "); } } printf("\n"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
C.
我们可以记录当前的位置
o
p
op
op以及目标位置
e
d
ed
ed。
如果在时刻
T
i
T_i
Ti，
o
p
=
e
d
op=ed
op=ed，那么就会执行命令
i
i
i。
并处理出时刻
T
i
+
1
T_{i+1}
Ti+1所在位置
d
d
d。如果
x
i
x_i
xi位于
o
p
op
op与
d
d
d之间，这说明这个命令有效。
代码：
#include <iostream> #include <cstdio> #include <cmath> #define LL long long const int maxn=1e5+7; using namespace std; int T,n; LL op,ed,ans; LL a[maxn],b[maxn]; int main() { scanf("%d",&T); while (T--) { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]); op=0,ed=0,ans=0; a[n+1]=2e10+1; for (int i=1;i<=n;i++) { if (op==ed) ed=b[i]; LL l=op,r; if (ed<op) { if (op-ed<=a[i+1]-a[i]) op=ed; else op-=a[i+1]-a[i]; } else { if (ed-op<=a[i+1]-a[i]) op=ed; else op+=a[i+1]-a[i]; } r=op; if (l>r) swap(l,r); if ((l<=b[i]) && (b[i]<=r)) ans++; } printf("%lld\n",ans); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
D.
考虑最少需要选多少个最小值与最大值。
以最小值为例，如果某一个数
x
x
x，
c
n
t
cnt
cnt为小于
x
x
x且没有出现在序列中并且没有匹配的数的个数。
显然如果
a
a
a在序列中且
c
n
t
cnt
cnt不为
0
0
0，则
c
n
t
−
1
cnt-1
cnt−1；
如果
a
a
a在序列中且
c
n
t
cnt
cnt为
0
0
0，此时必须取一个最小值，另一个数可以选择最大的没有出现的数（如果被选了就次大…）；
如果
a
a
a不存在则
c
n
t
+
1
cnt+1
cnt+1；
那么只要满足最少的最小值与最大值个数的方案都是合法的。
代码：
#include <iostream> #include <cstdio> const int maxn=2e5+7; using namespace std; int T,n,sum,l,r; int a[maxn]; int main() { scanf("%d",&T); while (T--) { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); a[n+1]=2*n+1; l=0,r=0; sum=0; for (int i=1;i<=n;i++) { sum+=a[i]-a[i-1]-1; if (!sum) l++; else sum--; } sum=0; for (int i=n;i>0;i--) { sum+=a[i+1]-a[i]-1; if (!sum) r++; else sum--; } printf("%d\n",n-r-l+1); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
E.
首先我们考虑第二类限制，显然只有当限制是若干条链的情况才是合法的。
我们可以把每条链缩成一个点，可以用并查集维护，集合的根设为链的开头。
对于第一类限制，我们设
(
x
,
y
)
(x,y)
(x,y)表示
x
x
x是
y
y
y的前置条件。
则如果
x
x
x与
y
y
y属于不同的链，那么我们从
y
y
y的链头向
x
x
x的链头连边。表示
x
x
x的链是
y
y
y的链的前置条件，因为每条链必须一次连续做完。
而如果
x
x
x与
y
y
y处于同一条链，则判断
x
x
x在链上的顺序是否在
y
y
y前面即可，不需要连边。
然后对新建的图跑top序，如果存在则有解。
代码：
#include <iostream> #include <cstdio> #include <vector> #include <queue> const int maxn=3e5+7; using namespace std; int n,m,x,y,cnt; int b[maxn],r[maxn],last[maxn],to[maxn],dep[maxn],v[maxn],p[maxn],ans[maxn]; vector <int> a[maxn]; queue <int> q; int find(int x) { if (!p[x]) return x; return p[x]=find(p[x]); } void uni(int x,int y) { int u=find(x),v=find(y); if (u!=v) p[u]=v; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d",&x); b[i]=x; } for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if ((!last[y]) && (find(x)!=find(y))) { last[y]=x; to[x]=y; uni(y,x); } else { printf("0\n"); return 0; } } for (int i=1;i<=n;i++) { if (!last[i]) { int x=i; while (x) { dep[x]=dep[last[x]]+1; x=to[x]; } } } for (int i=1;i<=n;i++) { int y=b[i]; if (!y) continue; if (find(i)!=find(y)) { a[find(y)].push_back(find(i)); r[find(i)]++; } else { if (dep[y]>dep[i]) { printf("0\n"); return 0; } } } for (int i=1;i<=n;i++) { if ((!p[i]) && (!r[i])) { q.push(i); v[i]=1; ans[++cnt]=i; } } while (!q.empty()) { int x=q.front(); q.pop(); for (int i=0;i<a[x].size();i++) { int y=a[x][i]; r[y]--; if ((!r[y]) && (!v[y])) { v[y]=1; q.push(y); ans[++cnt]=y; } } } for (int i=1;i<=n;i++) { if ((!p[i]) && (!v[i])) { printf("0\n"); return 0; } } for (int i=1;i<=cnt;i++) { int x=ans[i]; while (x) { printf("%d ",x); x=to[x]; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
F.
我们可以从
[
1
,
x
+
y
]
[1,x+y]
[1,x+y]选择一些数满足条件。
对于每一个选择的数
i
i
i，我们选上所有
i
≡
j
(
m
o
d
(
x
+
y
)
)
(
j
<
=
n
)
i≡j(mod\ (x+y))(j<=n)
i≡j(mod (x+y))(j<=n)，这样构造出的集合是合法的。
证明：显然在同一个区间内选的数一定是合法的，而如果跨区间。
如果不合法则满足
∣
p
+
(
x
+
y
)
−
q
∣
=
x
|p+(x+y)-q|=x
∣p+(x+y)−q∣=x或者
∣
p
+
(
x
+
y
)
−
q
∣
=
y
|p+(x+y)-q|=y
∣p+(x+y)−q∣=y，
化简得到
∣
p
−
q
∣
=
y
|p-q|=y
∣p−q∣=y，或者
∣
p
−
q
∣
=
x
|p-q|=x
∣p−q∣=x，与我们假设的区间内合法矛盾。
至于为什么这样构造出的集合 s i z e size size可以是最大的，可以参考cf的题解。
那么我们只需要考虑
[
1
,
x
+
y
]
[1,x+y]
[1,x+y]的每个数选还是不选即可，设
f
[
i
]
[
s
t
a
]
f[i][sta]
f[i][sta]表示前
i
i
i个数，选的数状态为
s
t
a
sta
sta的集合大小最大值。
维护状态
s
t
a
sta
sta可以知道
i
i
i能不能选，如果选了
i
i
i，集合增加的大小就是
i
≡
j
(
m
o
d
(
x
+
y
)
)
(
j
<
=
n
)
i≡j(mod\ (x+y))(j<=n)
i≡j(mod (x+y))(j<=n)。
我们可以令
x
>
y
x>y
x>y，那么
[
x
+
1
,
y
]
[x+1,y]
[x+1,y]的状态我们不需要记录，因为他们不会影响后面的转移。
所以复杂度就是
O
(
(
x
+
y
)
∗
2
m
a
x
(
x
,
y
)
)
O((x+y)*2^{max(x,y)})
O((x+y)∗2max(x,y))。
代码：
#include <iostream> #include <cstdio> #include <cmath> const int maxn=4200007; using namespace std; int n,x,y,p,l,r,ans; int f[2][maxn],bit[25]; int main() { scanf("%d%d%d",&n,&x,&y); if (x<y) swap(x,y); p=x+y; l=n/(x+y); r=n%(x+y); bit[0]=1; for (int i=1;i<=x;i++) bit[i]=bit[i-1]*2; int sta=0; for (int j=0;j<bit[x];j++) f[sta][j]=-0x3f3f3f3f; f[sta][0]=0; for (int i=1;i<=x+y;i++) { sta=1-sta; for (int j=0;j<bit[x];j++) f[sta][j]=f[1-sta][j]; for (int j=0;j<bit[x];j++) { if ((i-y>=1) && (j&bit[i-y-1])) continue; if ((i-x>=1) && (j&bit[i-x-1])) continue; if (i<=x) f[sta][j|bit[i-1]]=max(f[sta][j|bit[i-1]],f[1-sta][j]+l+(i<=r)); else f[sta][j]=max(f[sta][j],f[1-sta][j]+l+(i<=r)); } } ans=0; for (int j=0;j<bit[x];j++) ans=max(ans,f[sta][j]); printf("%d\n",ans); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
