A.Wrong Answer

给你两个整数 \(A\) 和 \(B\)，它们分别介于 \(0\) 和 \(9\) 之间。

请打印出不等于 \(A + B\) 的、介于 \(0\) 和 \(9\) 之间的整数。

两种方法

一种暴力

一种巧妙一点

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int  i=a;i>=ni--)
void solve()
{
    int a,b;
    cin>>a>>b;
    for(int i=0;i<10;i++)
    {
        if(i!=a+b)
        {
            cout<<i<<'\n';
            return;
        }
    }
}
int main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
}
1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << !(a + b) << '\n';
    return 0;
}

B.Adjacency Matrix

问题陈述

有一个简单的无向图 \(G\) ，其中有 \(N\) 个顶点，顶点上标有数字 \(1, 2, \ldots, N\)。

给你\(G\)的邻接矩阵\((A_{i,j})\)。也就是说，当且仅当 \(A_{i,j} = 1\) 时，\(G\) 有一条边连接顶点 \(i\) 和 \(j\)。

对于每个 \(i = 1, 2, \ldots, N\)，按升序打印与顶点 \(i\) 直接相连的顶点的编号。

这里，当且仅当顶点\(i\)和\(j\)之间有一条边相连时，顶点\(i\)和\(j\)才被认为是直接相连的。

B也有笨拙版和稍微灵活版的（没什么区别）

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= ni--)
const int N=105;
int a[105][105];
void solve()
{
int n;
cin>>n;
rep(i,1,n)
{
    rep(j,1,n)
    {
        cin>>a[i][j];
    }
}
rep(i,1,n)
{
    rep(j,1,n)
    {
        if(a[i][j])
        {
            cout<<j<<' ';
        }
    }
    cout<<'\n';
}

}
int main()
{
    int t = 1;
 //   cin>>t;
    while (t--)
    {
        solve();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

int main()
{
    int N;
    cin >> N;
    for (int T = 1; T <= N; ++T)
    {
        for (int i = 1, x; i <= N; ++i)
        {
            cin >> x;
            if (x)
                cout << i << ' ';
        }
        cout << '\n';
    }
    return 0;
}

C.343

给你一个正整数 \(N\)。

求一个不大于 \(N\) 的回折立方数的最大值。

这里，正整数 \(K\) 只有在满足以下两个条件时才被定义为回折立方数：

  • 有一个正整数\(x\)，使得\(x^3 = K\).
  • \(K\) 的十进制表示不含前导零，是一个宫调立方数。更确切地说，如果用介于\(0\)和\(9\)（含）之间的整数\(A_0, A_1, \ldots, A_{L-2}\)和介于\(1\)和\(9\)（含）之间的整数\(A_{L-1}\)将\(K\)表示为\(K = \sum_{i = 0}^{L-1} A_i10^i\)，则所有\(i = 0, 1, \ldots, L-1\)都是\(A_i = A_{L-1-i}\)。

暴力枚举三次方加上回文判断即可

开long long应该显而易见

下面还有一份比较高级的代码

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= ni--)
bool huiwen(ll x)
{
    ll y = 0;
    ll temp = x;
    //忘记这个了，草（）
    while (x)
    {
        y = y * 10 + x % 10;
        x /= 10;
    }
    if (temp == y)
    {
        return 1;
    }
    return 0;
}
int main()
{
    ll n;
    cin>>n;
    ll ans=1;
    for(ll i=1;i<n;i++)
    {
        ll x=i*i*i;
if(x>n||x>1e18)
{
    cout<<ans;
    return 0;
    //找不到啊，只能是1
}
else 
//回文判断即可
{
    if (huiwen(x))
    {
        ans=x;
    }
}
    }
    cout<<ans;
    //注意还要输出，有奇怪数据，不输出这个过不了一个点
    return 0;
}
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= ni--)
int main()
{

    ll N;
    cin >> N;

    ll ans = 0;
    for (ll a = 1; a * a * a <= N; a++)
    {
        string s = to_string(a * a * a);
        //转换
        if (s == string(s.rbegin(), s.rend()))
            //翻转判断
        { // 更简洁的回文判断
            ans = a * a * a;
        }
    }
    cout << ans << "\n";
    return 0;
}

D.Diversity of Scores

问题陈述

高桥正在举办一场有\(N\)名选手参加的比赛，选手编号为\(1\)至\(N\)。选手们将争夺积分。目前，所有棋手的积分都是零。

高桥的预知能力让他知道选手们的分数将如何变化。具体来说，对于\(i=1,2,\dots,T\)，\(A_i\)选手的分数将在\(i\)秒后增加\(B_i\)分。分数不会有其他变化。

高桥希望分数多样化，他想知道在每个时刻棋手的分数中会出现多少个不同的分数值。对于每个 \(i=1,2,\dots,T\)，求从现在起 \(i+0.5\) 秒钟后玩家分数中不同分值的数量。

例如，如果在某一时刻球员的得分分别为\(10\)、\(20\)、\(30\)和\(20\)，那么在该时刻球员的得分中有三个不同的分值。

输出

打印 \(T\) 行。第 \(i\) 行和第 \((1\leq i \leq T)\) 行应包含一个整数，代表\(i+0.5\)秒后球员得分中不同得分值的数量。

哈希就行

如果出现了一个新的答案就加加

如果能够减到0答案就减减

注意初始化

1
2
q[0]=n;
ans=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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n;i--)
map<ll,ll>q;
const int N=1e6+100;
ll a[N];
ll ans;
int main()
{
int n,t;
cin>>n>>t;
q[0]=n;
ans=1;
rep(i,1,t)
{
ll x,y;
cin>>x>>y;
if(q[a[x]]==1)
{
    ans--;
}
q[a[x]]--;
a[x]+=y;
if(q[a[x]]==0)
{
    ans++;
}
q[a[x]]++;
cout<<ans<<'\n';
}
}

E.7x7x7

问题陈述

在一个坐标空间中，我们想放置三个边长为\(7\)的立方体，这样正好一个、两个、三个立方体所包含区域的体积分别为\(V_1\)、\(V_2\)、\(V_3\)。

对于三个整数 \(a\)、\(b\)、\(c\)，让 \(C(a,b,c)\) 表示由 \((a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7)\) 代表的立方体区域。

请判断是否有满足下列所有条件的九个整数 \(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3\)，如果存在，请找出一个这样的元组。

  • \(|a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| \leq 100\)
  • 设 \(C_i = C(a_i, b_i, c_i)\ (i=1,2,3)\).
    • 恰好包含 \(C_1, C_2, C_3\) 中一个的区域的体积为 \(V_1\)。
    • 恰好包含两个 \(C_1, C_2, C_3\) 的区域的体积是 \(V_2\)。
    • 所有 \(C_1, C_2, C_3\) 所包含的区域的体积是 \(V_3\)。

输出

如果没有九个整数 \(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3\) 满足问题陈述中的所有条件，则打印 否。否则，按以下格式打印这些整数。如果存在多个解决方案，可以打印其中任何一个。

img

本题题目比较抽象

题目大意就是在一个三维坐标系上放置三个边长为7的立方体， 给出三个体积, 分别为三个立方体互不相交的体积、有且仅有任意两个立方体相交的体积和三个立方体相交的体积

要求输出一组符合要求的立方体的顶点的坐标，无解输出No.

由于都是7的边长

我们完全可以固定一个点0，0，0，然后暴力其他两个点，算面积

面积就是数学的问题了，自己画图好好加油罢

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
int s2(int x1,int y1,int z1,int x2,int y2,int z2)
{
    int ans=1;
    ans*=max(0,min(x1,x2)+7-max(x1,x2));
    ans*=max(0,min(y1,y2)+7-max(y1,y2));
    ans*=max(0,min(z1,z2)+7-max(z1,z2));
    return ans;
}
//求两两相交
int s3(int x1,int y1,int z1,int x2,int y2,int z2,int x3,int y3,int z3)
{
    int ans = 1;
    ans *= max(0, min({x1, x2,x3}) + 7 - max({x1, x2,x3}));
    ans *= max(0, min({y1, y2,y3}) + 7 - max({y1, y2,y3}));
    ans *= max(0, min({z1, z2,z3}) + 7 - max({z1, z2,z3}));
    return ans;
}
//求三三相交
int main()
{
int v1,v2,v3;
cin>>v1>>v2>>v3;
//输入
rep(x1,-7,7)
{
rep(y1,-7,7)
{
    rep(z1,-7,7)
    {
        rep(x2,-7,7)
        {
            rep(y2,-7,7)
            {
                rep(z2,-7,7)
                {
                    //固定0,0,0，枚举其余6个，使得范围确定
//求出公共部分要怎么求呢
int s_3 = s3(0, 0, 0, x1, y1, z1, x2, y2, z2);
//求三者公共
int s_2=s2(0,0,0,x1,y1,z1)+s2(0,0,0,x2,y2,z2)+s2(x1,y1,z1,x2,y2,z2)-3*s_3;
//求两两公共
int s_1=7*7*7*3-2*s_2-3*s_3;
//算出其余的
if(s_1==v1&&s_2==v2&&s_3==v3)
{
    cout<<"Yes"<<'\n';
    cout << "0 0 0 ";
    cout << x1 << ' ' << y1 << ' ' << z1 << ' ';
    cout << x2 << ' ' << y2 << ' ' << z2 << '\n';
    return 0;
    //检验合法性
}
                }
            }
        }
    }
}

}
cout<<"No";
return 0;
}



F - Second Largest Query

问题陈述

给你一个长度为 \(N\) 的序列 \(A = (A_1, A_2, \ldots, A_N)\)。

请按照给出的顺序处理 \(Q\) 个查询。每个查询属于以下两种类型之一：

  • 类型 \(1\)：以 1 p x 的形式给出。将 \(A_p\) 的值改为 \(x\)。
  • 类型 \(2\)：打印\((A_l, A_{l+1}, \ldots, A_r)\)中第二大数值的出现次数。更准确地说，打印满足\(l \leq i \leq r\)的整数\(i\)的个数，即在\(A_l, A_{l+1}, \ldots, A_r\)中正好有一个大于\(A_i\)的不同值。

毫无疑问线段树了（）

需要维护最大值，次大值，最大值数量，次大值数量

见代码：

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N=2e5+100;
int a[N];
int n, q;
struct tree
{
    int l, r;
    //左右儿子
    int maxn, remaxn;
    //最大，次大
    int mnum, rnum;
    //最大数量，次大数量
}w[4*N];
void pushup(tree& root,tree& left,tree& right)
{
    //根，左，右的比较
    if (left.maxn == right.maxn)
    {
        //相等的化那就一定是最大了，次大在两个次大找就可以
        root.maxn = left.maxn;
        root.mnum = left.mnum + right.mnum;
        if (left.remaxn == right.remaxn)
        {
            root.remaxn = left.remaxn;
            root.rnum = left.rnum + right.rnum;
        }
        else if (left.remaxn > right.remaxn)
        {
            root.remaxn = left.remaxn;
            root.rnum = left.rnum;
        }
        else if (left.remaxn < right.remaxn)
        {
            root.remaxn = right.remaxn;
            root.rnum = right.rnum;
        }
    }
    else if (left.maxn > right.maxn)
    //左大，那么次大还可以在右大和左次中找
    {
        root.maxn = left.maxn;
        root.mnum = left.mnum;
        if (left.remaxn == right.maxn)
        {
            root.remaxn = left.remaxn;
            root.rnum = left.rnum + right.mnum;
        }
        else if (left.remaxn > right.maxn)
        {
            root.remaxn = left.remaxn;
            root.rnum = left.rnum;
        }
        else if (left.remaxn < right.maxn)
        {
            root.remaxn = right.maxn;
            root.rnum = right.mnum;
        }
    }
    else if (left.maxn < right.maxn)
    {
        //和上面同理
        //这样就pushup好了
        root.maxn = right.maxn;
        root.mnum = right.mnum;
        if (left.maxn == right.remaxn)
        {
            root.remaxn = left.maxn;
            root.rnum = left.mnum + right.rnum;
        }
        else if (left.maxn > right.remaxn)
        {
            root.remaxn = left.maxn;
            root.rnum = left.mnum;
        }
        else if (left.maxn < right.remaxn)
        {
            root.remaxn = right.remaxn;
            root.rnum = right.rnum;
        }
    }
}
void build(int u,int l,int r)
{
    //建树
    if(l==r)
    {
        w[u]={l,r,a[l],0,1,0};
        //先初始最大
    }
    else
    {
        w[u]={l,r};
        //注意放坐标
        int mid=(l+r)>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(w[u],w[u*2],w[u*2+1]);
    }
}
void modify(int u,int p,int x)
{
    if(w[u].l==w[u].r&&w[u].l==p)
    {
        w[u].maxn=x;
        //到了，修改最大
    }
    else
    {
        int mid=(w[u].l+w[u].r)>>1;
        if(p<=mid)
        {
            modify(u*2,p,x);
            //左找
        }
        else 
        {
            modify(u*2+1,p,x);
            //右找
        }
        pushup(w[u],w[u*2],w[u*2+1]);
        //开始pushup
    }
}
tree query(int u,int l,int r)
{
if(w[u].l>=l&&w[u].r<=r)
{
    return w[u];
}
//包含直接返回
else 
{
    int mid=w[u].l+w[u].r>>1;
    tree x,y;
    int f1=0,f2=0;
    if(l<=mid)
{
        f1++;
        x=query(u*2,l,r);
}
    if(r>mid)
{
    f2++;
    y=query(u*2+1,l,r);
}
    if(f1&&f2)
    {
tree c={l,r};
pushup(c,x,y);
return c;
    }
    else
    {
        if(f1)
        {
            return x;
        }
        else
        {
            return y;
        }
    }

}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    rep(i,1,n)
    {
        cin>>a[i];
    }
    //输入
    build(1, 1, n);
    //建树
    while(q--)
    {
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1)
        {
modify(1,x,y);
//修改
        }
        else
        {
cout<<query(1,x,y).rnum<<'\n';
//查询次小数量
        }
    }
    
}