TEST 4
A 长方体
1 | signed main() { |
B 数括号
1 | string s; |
C. 哞哞哞
- 很有意思的递归去实现就好了
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
27using namespace std;
int l[105], n;
char find(int x, int y) {
if (x == 0) {
return (y == 1) ? 'm' : 'o';
}
if (y <= l[x - 1]) {
return find(x - 1, y);
}
if (y <= l[x] - l[x - 1]) {
return (y == 1 + l[x - 1]) ? 'm' : 'o';
}
return find(x - 1, y - l[x] + l[x - 1]);
}
signed main() {
IOS;
l[0] = 3;
for (int i = 1; i <= 24; i++) {
l[i] = i + 3 + 2 * l[i - 1];
}
cin >> n;
cout << find(24, n) << endl;
return 0;
}
D. 行路难
- 记录一下前后的状态用map搞一下就好了
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
122const int mn=1e5+5;
string s;
struct node
{
int x,y,f;
}pre[mn],nxt[mn];
map<pair<int,int>,bool>vis;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},ans;
pair<int,int> inc(int x,int y,int f,int dx,int dy)
{
if(f==0)
{
return make_pair(x+dx,y+dy);
}
if(f==1)
{
return make_pair(x+dy,y-dx);
}
if(f==2)
{
return make_pair(x-dx,y-dy);
}
if(f==3)
{
return make_pair(x-dy,y+dx);
}
return make_pair(-114514,1919810);
}
int main()
{
cin>>s;
int n=s.size();
s=' '+s;
nxt[n+1]=pre[0]=(node){0,0,0};
for(int i=1;i<=n;i++)
{
pre[i]=pre[i-1];
if(s[i]=='R')
{
pre[i].f=(pre[i].f+1)%4;
}
if(s[i]=='L')
{
pre[i].f=(pre[i].f+3)%4;
}
if(s[i]=='F')
{
pre[i].x+=dx[pre[i].f];
pre[i].y+=dy[pre[i].f];
}
}
for(int i=n;i>=1;i--)
{
nxt[i]=nxt[i+1];
if(s[i]=='R')
{
nxt[i].f=(nxt[i].f+3)%4;
}
if(s[i]=='L')
{
nxt[i].f=(nxt[i].f+1)%4;
}
if(s[i]=='F')
{
nxt[i].x-=dx[nxt[i].f];
nxt[i].y-=dy[nxt[i].f];
}
}
for(int i=n;i>=1;i--)
{
if(nxt[i].f==1)
{
swap(nxt[i].x,nxt[i].y);
nxt[i].y*=-1;
}
if(nxt[i].f==0)
{
nxt[i].x*=-1;
nxt[i].y*=-1;
}
if(nxt[i].f==3)
{
swap(nxt[i].x,nxt[i].y);
nxt[i].x*=-1;
}
nxt[i].f=(4-nxt[i].f)%4;
}
int tx,ty;
for(int i=1;i<=n;i++)
{
if(s[i]!='L')
{
pair<int,int> t=inc(pre[i-1].x,pre[i-1].y,(pre[i-1].f+3)%4,nxt[i+1].x,nxt[i+1].y);
if(!vis[t])
{
vis[t]=1;
ans++;
}
}
if(s[i]!='R')
{
pair<int,int> t=inc(pre[i-1].x,pre[i-1].y,(pre[i-1].f+1)%4,nxt[i+1].x,nxt[i+1].y);
if(!vis[t])
{
vis[t]=1;
ans++;
}
}
if(s[i]!='F')
{
pair<int,int> t=inc(pre[i-1].x+dx[pre[i-1].f],pre[i-1].y+dy[pre[i-1].f],pre[i-1].f,nxt[i+1].x,nxt[i+1].y);
if(!vis[t])
{
vis[t]=1;
ans++;
}
}
}
cout << ans << endl;
return 0;
}
E. 来贴贴
- 用线段树去维护一下就好了
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
int w[4 * MAX];
int n, m;
void pushup(int u) {
w[u] = max(w[u * 2], w[u * 2 + 1]);
}
void build(int u, int L, int R) {
if (L == R) {
w[u] = m;
return ;
}
int M = (L + R) / 2;
build(u * 2, L, M), build(u * 2 + 1, M + 1, R);
pushup(u);
}
void update(int u, int L, int R, int x, int y) {
if (L == R) {
w[u] -= y;
return ;
}
int M = (L + R) / 2;
if (x <= M) update(u * 2, L, M, x, y);
else update(u * 2 + 1, M + 1, R, x, y);
pushup(u);
}
int query(int u, int L, int R, int x) {
if (L == R) {
return L;
}
if (w[u] < x) return -1;
int M = (L + R) / 2;
if (w[u * 2] < x) return query(u * 2 + 1, M + 1, R, x);
else return query(u * 2, L, M, x);
}
signed main() {
IOS;
cin >> n >> m;
build(1, 1, n);
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
int idx = query(1, 1, n, x);
cout << idx << endl;
if (idx > 0) {
update(1, 1, n, idx, x);
}
}
return 0;
}
F. 剪包锤
- 有点状态机了
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/*
线性dp题
令f[i][j][k]表示前i盘当前出拳为j改变了k次的最多赢的次数。
出拳设置H:2, S:1, P:0
第i个出招为s[i]，如果(j-s[i]+3)%3==1，则可以赢，转移有：
f[i][j][k] <- f[i-1][j][k]+1
否则转移有：
f[i][j][k] <- f[i-1][j][k]
枚举当前出拳为jj，如果(jj-s[i]+3)%3==1，则可以赢，转移有：
f[i][jj][k+1] <- f[i-1][j][k]+1
否则转移有：
f[i][jj][k+1] <- f[i-1][j][k]
最后答案为max(f[n][j][k])
可以优化状态将改变k次改为最多改变k次，可以省点时间。
*/
using namespace std;
const int M=100005;
int n,K,f[M][3][25],ans;
int chg(char c){
if(c=='H') return 2;
if(c=='S') return 1;
return 0;
}
int main(){
scanf("%d%d",&n,&K);
//f[0][0/1/2][0]=0
for(int i=1; i<=n; i++){
char s[3]; scanf("%s",s);
int t=chg(s[0]);
for(int j=0; j<=2; j++){
for(int k=K; k>=0; k--){
if((j-t+3)%3==1) f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+1);
else f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
int jj=(j+1)%3;
if((jj-t+3)%3==1) f[i][jj][k+1]=max(f[i][jj][k+1],f[i-1][j][k]+1);
else f[i][jj][k+1]=max(f[i][jj][k+1],f[i-1][j][k]);
jj=(j+2)%3;
if((jj-t+3)%3==1) f[i][jj][k+1]=max(f[i][jj][k+1],f[i-1][j][k]+1);
else f[i][jj][k+1]=max(f[i][jj][k+1],f[i-1][j][k]);
}
}
}
for(int j=0; j<=2; j++)
for(int k=0; k<=K; k++)
ans=max(ans,f[n][j][k]);
printf("%d",ans);
return 0;
}
G
- 只要把大于x为+1，小于x为-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
25const int M=100005;
int n,X,sum[M*2],C[M*2];
ll ans;
void add(int x,int y){
for(int i=x; i<=n*2; i+=i&-i)
C[i]+=y;
}
int ask(int x){
int ret=0;
for(int i=x; i; i-=i&-i) ret+=C[i];
return ret;
}
int main(){
scanf("%d%d",&n,&X);
sum[0]=n; add(sum[0],1);
for(int i=1; i<=n; i++){
int a; scanf("%d",&a);
if(a>=X) sum[i]=sum[i-1]+1;
else sum[i]=sum[i-1]-1;
ans+=ask(sum[i]);
add(sum[i],1);
}
printf("%lld",ans);
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ysmmm的快乐小屋！
