AtCoder 初学者竞赛 343 解决问题

A.Wrong Answer（模拟）

题意：

给两个整数$ A $ 和 \(B\)，两个数都在 \(0\) 和 \(9\) 之间，包括 \(0\) 和 \(9\)

打印不等于\(A+B\) 的任何整数输出 （包括 \(0\) 和 \(9\)）

分析：

判断方式很多，我想的是只有两个数都为 \(0\) ，\(A+B==\) \(0\)

那我们直接判断，当\(A \;and\;B\) 为 \(0\) ，输出 \(1\) 否则输出 \(0\)

代码：

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int a,b;
	cin >> a >> b;
	if(a==0&&b==0) cout << 1;
	else cout << 0;
	return 0;
}

B.Adjacency Matrix（邻接矩阵）

题意：

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

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

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

这里，当且仅当存在连接顶点 \(i\) 和 \(j\) 的边时，称顶点 \(i\) 和 \(j\) 是直接连通的。

分析：

其实就是邻接矩阵的存图方式，直接给了你存完边的图

\(i\) 表示当前节点，\(j\) 表示与点 \(i\) 相邻的节点

直接从左到右遍历输出 \(A_{ij}==1\) 的点即可

代码：

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,g[105][105];
	cin >> n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin >> g[i][j];
			if(g[i][j]==1){
				cout << j << " ";
			}
		}
		cout << endl;
	}
	return 0;
}

C.343（模拟）

题意：

给一个整数 \(n\) （\(1 \le n \le 10^{18}\)）

找一个数 $ x$（\(1 \le x \le n\)），\(x\) 需满足是回文数，且 \(x\) 为 \(x = k^{3}\)，$k $为正整数

输出满足条件且小于等于 \(n\) 的最大 \(x\)

分析：

枚举小于等于 $n $ 的立方数，然后在判断是否回文即可，从小到大枚举或者从大到小都可

但要注意范围，还有如果使用 \(pow\) 函数是不可以的，因为 \(pow\) 传参数为 \(double\) 类型

代码：

#include <bits/stdc++.h>
using namespace std;

bool ish(long long x) {
	string s = to_string(x);
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, res = -1; // 初始化为 -1，以便判断是否存在满足条件的立方数
    cin >> n;
    // 从小到大搜索立方数
    for (long long i = 0; i * i * i <= n; i++) {
        if (ish(i*i*i)) {
            res = i * i * i; // 更新最大的满足条件的立方数
        }
    }
    cout << res;
    return 0;
}

D.Diversity of Scores（哈希表）

题意：

题目给出 \(N\) 个选手，\(T\) 次操作。每位选手都有积分，开始所有选手的积分都为 \(0\)

对于每次操作，输出一个整数表示有几种不同的积分（\(0\) 也算一种不同的分数）。

分析：

需要知道几种不同的积分，哈希表的性质就是只能加不同的元素，有多少种积分可以对应哈希表元素数量

$key $ 对应积分的值 \(value\) 对应积分的出现次数，当我们出现次数为 \(0\) 时去除该元素

每次操作打印哈希表元素数量

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    long long g[200005]={};
    cin >> n >> m;
    map<long long,int> mp;//第一个值表示出现元素，第二个值出现次数
    mp[0] = n;//初始0出现次数为n
    while(m--){
    	int a,b;
    	cin >> a >> b;
    	mp[g[a]] --;//原始出现积分次数减1
    	if(mp[g[a]]==0) mp.erase(g[a]);//如果出现次数为0删掉此元素
    	g[a] += b;//积分变化
    	mp[g[a]] ++;//变化后的积分出现次数加1
    	cout << mp.size() << endl;
    }
    return 0;
}

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\),输出 \(9\) 个数表示满足\(V_{1},V_{2},V_{3}\)条件的三个立方体坐标\(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3\)

分析：

三维就是二维多一维，可以先思考一下二维正方形的话，有没有什么规律

得到了关键信息三个正方形面积和\(V_{1},V_{2},V_{3}\)的关系，对于三维就是我们再加上 \(z\) 轴即可

\(V_{1}+2*V_{2}+3*V_{3}=7*7*7*3\)

那我们如果符合上述公式，即可以找到输出Yes否则输出No

只有区域之间的相对位置才是最重要的，因此我们可以固定其中一个区域，可以将\(C_1\)的坐标都设为 \(0\)

• \(v_3=V(C_1\cap C_2\cap C_3)\)

• \(v_2=V(C_1\cap C_2)+V(C_1\cap C_3)+V(C_2\cap C_3)-3v_3\)

• \(v_1=3\times 7^3-2v_2-3v_3\)

枚举第二个正方体和第三个正方体找到合适的，范围\((-7，7)\)，找到合适的我们就结束

代码：

#include <bits/stdc++.h>
using namespace std;

int f(int a1,int b1,int c1,int a2,int b2,int c2){
	int res = 1;
	res *= max(0,min(a1,a2)+7-max(a1,a2));
	res *= max(0,min(b1,b2)+7-max(b1,b2));
	res *= max(0,min(c1,c2)+7-max(c1,c2));
	return res;
}

int f(int a1,int b1,int c1,int a2,int b2,int c2,int a3,int b3,int c3){
	int res = 1;
	res *= max(0, min({a1, a2, a3}) + 7 - max({a1, a2, a3}));
    res *= max(0, min({b1, b2, b3}) + 7 - max({b1, b2, b3}));
    res *= max(0, min({c1, c2, c3}) + 7 - max({c1, c2, c3}));
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int v1,v2,v3;
    cin >> v1 >> v2 >> v3;
    if(v1+2*v2+3*v3!=7*7*7*3){
    	cout << "No" << endl;
   		return 0;
    }
    cout << "Yes" << endl;
    for(int a1=-7;a1<=7;a1++){
    	for(int b1=-7;b1<=7;b1++){
    		for(int c1=-7;c1<=7;c1++){
    			for(int a2=-7;a2<=7;a2++){
    				for(int b2=-7;b2<=7;b2++){
    					for(int c2=-7;c2<=7;c2++){
    						int t3 = f(0,0,0,a1,b1,c1,a2,b2,c2);
    						int t2 = f(0,0,0,a1,b1,c1)+f(0,0,0,a2,b2,c2)+f(a1,b1,c1,a2,b2,c2)-3*t3;
    						if(t2==v2&&t3==v3){
    							cout << 0 << " " << 0 << " " << 0 << " ";
    							cout << a1 << " " << b1 << " " << c1 << " ";
    							cout << a2 << " " << b2 << " " << c2 ;
    							return 0;
    						}
    						
    					}
    				}
    			}
    		}
    	}
    }
    return 0;
}