2025/2/19 心得
第一道题。
M. D - Banned K (AI)
题目描述
我们有NN个球。第ii个球上写着一个整数A_iAi。
对于每个k=1,2,...,Nk=1,2,...,N，解决以下问题并打印答案。
- 找到从除第kk个球以外的N-1N−1个球中选择两个不同球（忽略顺序）的方法数，使它们上面写的整数相等。
约束条件
-
3 \leq N \leq 2 \times 10^53≤N≤2×105
-
1 \leq A_i \leq N1≤Ai≤N
-
输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
NN
A_1A1 A_2A2 ...... A_NAN
输出
对于每个k=1,2,...,Nk=1,2,...,N，打印一行包含答案。
样例输入1
5
1 1 2 1 2
样例输出1
2
2
3
2
3
考虑例如k=1k=1的情况。其他球上的数字是1,2,1,21,2,1,2。
从这些球中，有两种方式选择两个不同的球，使它们上面写的整数相等。
因此，k=1k=1的答案为22。
样例输入2
4
1 2 3 4
样例输出2
0
0
0
0
没有两个球上写着相同的数字。
样例输入3
5
3 3 3 3 3
样例输出3
6
6
6
6
6
任何两个球上都有相同的数字。
这道题的思路是？求出所有相同的面积。再把他们统一列我给列出一共有多少种组合？最后再减去去掉的那哥也就是
当前这个数在数组中存在的次数减一就行了。
我的初始代码如下，
#include<bits/stdc++.h>
using namespace std;
int n,a[200010],b[200010];
long long sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]++;
}
for(int i=1;i<=n;i++)
{
sum+=b[i]*(b[i]-1)/2;
}
for(int i=1;i<=n;i++)
{
cout<<sum-(b[a[i]]-1)<<endl;
}
return 0;
}
但这样只能得到60分儿。
经过我检查，我发现有些数据是超时的。
所以我们就需要用到I1ll
#include<bits/stdc++.h>
using namespace std;
int n,a[200010],b[200010];
long long sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]++;
}
for(int i=1;i<=n;i++)
{
sum+=1LL*b[i]*(b[i]-1)/2;//gdsg
}
for(int i=1;i<=n;i++)
{
cout<<sum-(b[a[i]]-1)<<endl;
}
return 0;
}
第二题
N. C - Replacing Integer (AI)
题目描述
给定任意整数 xx，Aoki 可以进行以下操作。
操作：将 xx 替换为 xx 和 KK 的绝对差。
给定整数 NN 的初始值。找到 Aoki 进行零次或多次操作后 NN 可能取到的最小值。
约束条件
-
0 ≤ N ≤ 10^{18}0≤N≤1018
-
1 ≤ K ≤ 10^{18}1≤K≤1018
-
输入中的所有值都是整数。
输入
从标准输入以以下格式给出输入：
NN KK
输出
打印 Aoki 进行零次或多次操作后 NN 可能取到的最小值。
样例输入 1
7 4
样例输出 1
1
最初，N=7N=7。
经过一次操作，NN 变为 |7-4| = 3∣7−4∣=3。
经过两次操作，NN 变为 |3-4| = 1∣3−4∣=1，这是 NN 可能取到的最小值。
样例输入 2
2 6
样例输出 2
2
N=2N=2 在零次操作后是最小值。
样例输入 3
1000000000000000000 1
样例输出 3
0
这道题我本来一开始用if去做。
居然还得了58分儿。
原本代码如下
#include<bits/stdc++.h>
using namespace std;
long long n,a,b,k;
long long sum;
int main()
{
cin>>n>>k;
if(n<=k)
{
cout<<n;
}
else if(k==1)
{
cout<<"0";
}
else
{
if(n%k==0)
{
cout<<"0";
}
else
{
cout<<"1";
}
}
return 0;
}
但这道题其实只需要找n模key的差值。
然后再用key减这个差值。
最后比较一下这两个值就行了。
代码如下
#include<bits/stdc++.h>
using namespace std;
long long n,a,b,k;
long long sum;
int main()
{
cin>>n>>k;
a=n%k;
b=k-(n%k);
cout<<min(a,abs(b));
return 0;
}
第三题。
O. D - Flipping Signs (AI)
题目描述
给定一个整数序列 A\_1, A\_2, ..., A\_NA_1,A_2,...,A_N，你可以对这个整数序列进行以下操作任意次数：
操作：选择一个整数 ii，满足 1 \leq i \leq N-11≤i≤N−1。将 A\_iA_i 和 A\_{i+1}A_i+1 都乘以 -1−1。
求经过你的操作后，整数序列 B\_1, B\_2, ..., B\_NB_1,B_2,...,B_N 的最大可能和。
约束
-
输入的所有值都是整数。
-
2 \leq N \leq 10^52≤N≤105
-
-10^9 \leq A\_i \leq 10^9−109≤A_i≤109
输入
从标准输入中以以下格式给出输入：
NN
A_1A1 A_2A2 ...... A_NAN
输出
打印出 B\_1 + B\_2 + ... + B\_NB_1+B_2+...+B_N 的最大可能值。
样例输入 1
3
-10 5 -4
样例输出 1
19
如果我们按照以下操作进行：
- 选择 11 作为 ii，将序列变为 10, -5, -410,−5,−4。
- 选择 22 作为 ii，将序列变为 10, 5, 410,5,4。
我们得到 B\_1 = 10, B\_2 = 5, B\_3 = 4B_1=10,B_2=5,B_3=4。这里的和，B\_1 + B\_2 + B\_3 = 10 + 5 + 4 = 19B_1+B_2+B_3=10+5+4=19，是最大可能的结果。
样例输入 2
5
10 -4 -8 -11 3
样例输出 2
30
样例输入 3
11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000
样例输出 3
10000000000
输出可能无法适应 3232 位整数类型。
这道题我一开始并没有什么思路
我本来想用很多种条件把它给判断出来。
嗯但其实不然。
我们只需要找这个最小值的数量。
如果
它是偶数，就把所有最小值和所有值的绝对值加起来就行了。
如果是奇数的话，那么就是用所有值的绝对值之和减去最小值的绝对值乘二
代码如下
#include<bits/stdc++.h>
using namespace std;
long long n,b,c,a[100100],s,sum2,sum3,n1,n2=99999999;
char a1;
int main(){
// freopen("loop.in","r",stdin);
// freopen("loop.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]<0)
s++;
n1+=abs(a[i]);
if(abs(a[i])<n2)
n2=abs(a[i]);
}
if(s%2==0)
cout<<n1;
else
cout<<n1-2*n2;
return 0;
}