比赛链接
CE是暴力，D是数据结构题，F是线段树。这场的E比较有意思，其他的感觉有点水。
A - Wrong Answer
题意：
给你两个数 A , B A,B A,B ( 0 ≤ A , B ≤ 9 ) (0\le A,B\le 9) (0≤A,B≤9)，返回一个个位数，使得它不等于 A + B A+B A+B。
思路：
看一下 A + B A+B A+B 等不等于 0 0 0 ，如果不等于就直接输出 0 0 0，如果正好等于就随便找个其他数输出即可。
code：
#include <iostream>
#include <cstdio>
using namespace std;
int a,b;
int main(){
cin>>a>>b;
if(a+b==0)cout<<9<<endl;
else cout<<0<<endl;
return 0;
}
B - Adjacency Matrix
题意：
给你一个 N N N 个点的无向图和 N × N N\times N N×N 的邻接矩阵。问每个点的邻接点有哪些。
思路：
因为是无向图，所以邻接矩阵是对称的，我们把第 i i i 行或者第 i i i 列看成 i i i 的出边都没有问题。假如第 i i i 行上的某个位置 A i , j = 1 A_{i,j}=1 Ai,j=1 就说明 i → j i\rightarrow j i→j 有一条边，就相当于 j j j 是 i i i 的一个邻接点，我们直接遍历第 i i i 行就能找到 i i i 的所有邻接点了。
code：
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1,t;j<=n;j++){
cin>>t;
if(t==1)cout<<j<<" ";
}
cout<<endl;
}
return 0;
}
C - 343
题意：
给你一个数 N N N ( 1 ≤ N ≤ 1 0 18 ) (1\le N\le 10^{18}) (1≤N≤1018)，问不超过 N N N 的 最大立方数 同时是 回文数 的数是什么。
思路：
不难发现，如果这个数是立方数，那么它最多只有 1 0 6 10^6 106 种可能，再在其中找到回文数即可。而判断回文最多只需要判断 18 18 18 位，所以直接暴力枚举就能找到所有可能的立方数且是回文数的数。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll n;
bool check(ll x){
string s=to_string(x);
int len=s.length();
for(int i=0;i<len/2;i++)
if(s[i]!=s[len-i-1])
return false;
return true;
}
int main(){
cin>>n;
ll ans;
for(ll i=1;i*i*i<=n;i++)
if(check(i*i*i))
ans=i*i*i;
cout<<ans<<endl;
return 0;
}
D - Diversity of Scores
题意：
有 N N N 个人， T T T 次修改操作，一开始所有人分数都是 0 0 0。
每次修改操作形如 a b ，表示将第
a
a
a 个人的分数加上
b
b
b。
问每次修改后，有多少种不同的分数。
思路：
用 m a p map map 记录每种分数有几个人，每次修改结束后看一下 m a p map map 中有几种分数就行了。
code：
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int n,t;
ll a[maxn];
int main(){
cin>>n>>t;
map<ll,int> mp;
mp[0]=n;
for(int i=1,idx,b;i<=t;i++){
cin>>idx>>b;
mp[a[idx]]--;
if(mp[a[idx]]==0)mp.erase(a[idx]);
a[idx]+=b;
mp[a[idx]]++;
cout<<mp.size()<<endl;
}
return 0;
}
E - 7x7x7
题意：
在三维直角坐标系中有两个边长为 7 7 7 的正六面体（就是立方体）。我们用立方体左下角的点的坐标描述一个立方体的位置，具体来说，就是用 C ( a , b , c ) C(a,b,c) C(a,b,c) 描述 ( a ≤ x ≤ a + 7 ) ∧ ( b ≤ y ≤ b + 7 ) ∧ ( c ≤ z ≤ c + 7 ) (a\le x\le a+7)\wedge (b\le y\le b+7)\wedge (c\le z\le c+7) (a≤x≤a+7)∧(b≤y≤b+7)∧(c≤z≤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 a1,b1,c1,a2,b2,c2,a3,b3,c3 描述三个正方体的位置，其中第 i i i 个立方体的位置为 C i = ( a i , b i , c i ) C_i=(a_i,b_i,c_i) Ci=(ai,bi,ci)。并且 ∣ a 1 ∣ , ∣ b 1 ∣ , ∣ c 1 ∣ , ∣ a 2 ∣ , ∣ b 2 ∣ , ∣ c 2 ∣ , ∣ a 3 ∣ , ∣ b 3 ∣ , ∣ c 3 ∣ ≤ 100 |a_1|,|b_1|,|c_1|,|a_2|,|b_2|,|c_2|,|a_3|,|b_3|,|c_3|\le 100 ∣a1∣,∣b1∣,∣c1∣,∣a2∣,∣b2∣,∣c2∣,∣a3∣,∣b3∣,∣c3∣≤100。
定义：
- 在 C 1 , C 2 , C 3 C_1,C_2,C_3 C1,C2,C3 中只包含在一个立方体内部的体积为 V 1 V_1 V1。
- 在 C 1 , C 2 , C 3 C_1,C_2,C_3 C1,C2,C3 中只包含在两个立方体内部的体积为 V 2 V_2 V2。
- 在 C 1 , C 2 , C 3 C_1,C_2,C_3 C1,C2,C3 中包含在三个立方体内部的体积为 V 3 V_3 V3。
给你 V 1 , V 2 , V 3 V_1,V_2,V_3 V1,V2,V3，问可行的一组 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 a1,b1,c1,a2,b2,c2,a3,b3,c3。
思路：
乍一看根本无从下手，但是看到数据范围很小，感觉应该是个比较暴力的做法。
先想两个立方体的情况。如果两个立方体有相交，那么相交的区域的上边界应该是两个立方体的上边界的较小值（也就是靠下的那个边界）。同理，相交区域的下边界应该是两个立方体下边界的较大值（也就是靠上的那个边界）。相交区域的左边界应该是两个立方体左边界的较大值。相交区域的右边界应该是两个立方体右边界的较小值。相交区域的前边界应该是两个立方体前边界的较大值。相交区域的后边界应该是两个立方体后边界的较小值。
这样只要知道了两个立方体的位置，就可以 O ( 1 ) O(1) O(1) 地得到相交区域的位置，也就得到了这个区域的体积。显然的如果算出来的上边界低于下边界，那么就说明不存在这个相交区域，同理，右边界要大于左边界，后边界要大于前边界。而对于三个立方体的相交区域我们也可以这样得到。
因此我们只要知道了三个立方体的位置，就可以算出两两相交的区域体积，和三个立方体的相交区域，根据容斥的思想可以很容易算出它们的 V 1 , V 2 , V 3 V_1,V_2,V_3 V1,V2,V3。
但是如何确定这三个立方体的位置呢，根据相对论，如果有一种可行的三立方体位置，那么我们可以把中间那个立方体的左下角点位置放在原点。前面说了数据范围很小，某个立方体要么和一个立方体相交，要么就相离。而相离的话，离多远都可以，那么不如就让它贴着前一个立方体。这样的话，三个立方体就算一起贴着，点能遍及到的位置就只有 { ( x , y , z ) ∣ − 7 ≤ x ≤ 7 , − 7 ≤ y ≤ 7 , − 7 ≤ z ≤ 7 } \{(x,y,z)|-7\le x\le 7,-7\le y\le 7,-7\le z\le 7\} {(x,y,z)∣−7≤x≤7,−7≤y≤7,−7≤z≤7}。总的点的可能不会超过 1 5 3 = 3375 15^3=3375 153=3375，暴力枚举两个立方体的点的位置时间复杂度也就是 1 e 7 1e7 1e7，完全能跑。所以暴力就完了。
这里把中间那个立方体放在原点可以考虑到所有相对位置的情况。而把一边的立方体放在原点有可能会漏掉一部分情况，就像下面那个写法。所以三维的还是把中间的模型放在原点比较好。
code：
#include <iostream>
#include <cstdio>
using namespace std;
int v1,v2,v3;
inline int gv(int x1,int y1,int z1,int x2,int y2,int z2){
int xl,xu,yl,yu,zl,zu;
xl=max(x1,x2);
xu=min(x1,x2)+7;
yl=max(y1,y2);
yu=min(y1,y2)+7;
zl=max(z1,z2);
zu=min(z1,z2)+7;
if(xl<xu && yl<yu && zl<zu)return (xu-xl)*(yu-yl)*(zu-zl);
else return 0;
}
inline int gv(int x1,int y1,int z1,int x2,int y2,int z2,int x3,int y3,int z3){
int xl,xu,yl,yu,zl,zu;
xl=max(max(x1,x2),x3);
xu=min(min(x1,x2),x3)+7;
yl=max(max(y1,y2),y3);
yu=min(min(y1,y2),y3)+7;
zl=max(max(z1,z2),z3);
zu=min(min(z1,z2),z3)+7;
if(xl<xu && yl<yu && zl<zu)return (xu-xl)*(yu-yl)*(zu-zl);
else return 0;
}
int main(){
cin>>v1>>v2>>v3;
for(int x1=-7,tot=1029,ab,bc,ac,abc,V1,V2,V3;x1<=15;x1++)
for(int y1=-7;y1<=15;y1++)
for(int z1=-7;z1<=15;z1++)
for(int x2=-7;x2<=15;x2++)
for(int y2=-7;y2<=15;y2++)
for(int z2=-7;z2<=15;z2++){
ab=gv(0,0,0,x1,y1,z1);
bc=gv(x1,y1,z1,x2,y2,z2);
ac=gv(0,0,0,x2,y2,z2);
abc=gv(0,0,0,x1,y1,z1,x2,y2,z2);
V3=abc;
V2=ab+bc+ac-3*V3;
V1=tot-2*(ab+bc+ac-abc)+abc;
if(V1==v1 && V2==v2 && V3==v3){
printf("Yes\n%d %d %d %d %d %d %d %d %d\n",0,0,0,x1,y1,z1,x2,y2,z2);
return 0;
}
}
puts("No");
return 0;
}
F - Second Largest Query
题意：
有一个 N N N 个数的序列 A 1 , A 2 , A 3 , … , A N A_1,A_2,A_3,\dots,A_N A1,A2,A3,…,AN。
有 Q Q Q 次操作，操作有两种：
1 p x：表示将 A p A_p Ap 赋值为 x x x。2 l r：表示询问区间 [ l , r ] [l,r] [l,r] 的次大值的个数。
思路：
这种问法一眼线段树，主要是如何维护次大值。
在两个区间进行合并的时候，有可能成为次大值的可能是左区间的最大值，次大值，右区间的最大值次大值。所以每个区间我们要维护区间最大值和次大值。而询问的是次大值的个数，所以我们最大值和次大值的个数也要维护。
写起来情况讨论比较麻烦，其他还好。
code：
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;
int n,q;
struct segment_tree{
#define ls p<<1
#define rs p<<1|1
int n;
struct Node{
int m1,m2,c1,c2;
Node(int m1=0,int m2=0,int c1=0,int c2=0):m1(m1),m2(m2),c1(c1),c2(c2){};
}tr[maxn<<2];
Node merge_Node(Node a,Node b){
Node t;
if(a.m1==b.m1){
t.m1=a.m1;
t.c1=a.c1+b.c1;
if(a.m2==b.m2){
t.m2=a.m2;
t.c2=a.c2+b.c2;
}
else if(a.m2>b.m2){
t.m2=a.m2;
t.c2=a.c2;
}
else {
t.m2=b.m2;
t.c2=b.c2;
}
}
else if(a.m1>b.m1){
t.m1=a.m1;
t.c1=a.c1;
if(a.m2==b.m1){
t.m2=a.m2;
t.c2=a.c2+b.c1;
}
else if(a.m2>b.m1){
t.m2=a.m2;
t.c2=a.c2;
}
else {
t.m2=b.m1;
t.c2=b.c1;
}
}
else {
t.m1=b.m1;
t.c1=b.c1;
if(a.m1==b.m2){
t.m2=a.m1;
t.c2=a.c1+b.c2;
}
else if(a.m1>b.m2){
t.m2=a.m1;
t.c2=a.c1;
}
else {
t.m2=b.m2;
t.c2=b.c2;
}
}
return t;
}
void print(int p,int l,int r){
printf("%2d:[%d,%d] %d %d|%d %d\n",p,l,r,tr[p].m1,tr[p].c1,tr[p].m2,tr[p].c2);
if(l==r)return;
int mid=(l+r)>>1;
print(ls,l,mid);
print(rs,mid+1,r);
}
void print(){
print(1,1,n);
}
void build(int p,int l,int r){
if(l==r){
cin>>tr[p].m1;
tr[p].c1=1;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
tr[p]=merge_Node(tr[ls],tr[rs]);
}
void build(int _n){
n=_n;
build(1,1,n);
}
void mdy(int p,int l,int r,int idx,int x){
if(l==r){
tr[p].m1=x;
return;
}
int mid=(l+r)>>1;
if(idx<=mid)mdy(ls,l,mid,idx,x);
else mdy(rs,mid+1,r,idx,x);
tr[p]=merge_Node(tr[ls],tr[rs]);
}
Node query(int p,int l,int r,int L,int R){
if(L<=l && r<=R){
return tr[p];
}
int mid=(l+r)>>1;
if(R<=mid)return query(ls,l,mid,L,R);
else if(L>mid)return query(rs,mid+1,r,L,R);
else return merge_Node(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
int opt(int op,int a,int b){
if(op==1)mdy(1,1,n,a,b);
else {
return query(1,1,n,a,b).c2;
}
return 0;
}
#undef ls
#undef rs
}tr;
int main(){
cin>>n>>q;
tr.build(n);
// tr.print();
// puts("");
for(int i=1,op,a,b;i<=q;i++){
cin>>op>>a>>b;
if(op==2)cout<<tr.opt(op,a,b)<<endl;
else tr.opt(op,a,b);
// tr.print();
// puts("");
}
return 0;
}
