第一题题意是给你一个只有2个数的数组，一个重复，一个不重复。求不重复的数的下标。标记数组即可。
博客链接
https://blog.csdn.net/yueshehanjiang/article/details/115593830?spm=1001.2014.3001.5501
#include<bits/stdc++.h>
using namespace std;
#define re register int
typedef long long ll ;
const int N = 110 ;
int n , t ;
int a[N] ;
int s[N] ;
int main()
{
cin >> t ;
while(t--)
{
memset(s,0,sizeof s) ;
cin >> n ;
for(int i = 1 ; i <= n ; i ++ )
{
int x ;
cin >> a[i] ;
s[a[i]] ++ ;
}
int y = 0 ;
for(int i = 1 ; i <= 100 ; i ++)
{
if(s[i] == 1) y = i ;
}
for(re i = 1 ; i <= n ; i ++)
{
if(a[i] == y) cout << i << endl;
}
}
return 0 ;
}
第二题给你一个n×n的字符数组，其中有2个点为，其余点都为.，求如何把2个.变成，使得4个*成为最近的矩形。模拟即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
int t , n ;
const int N = 410 ;
char a[N][N] ;
int main()
{
cin >> t ;
while(t--)
{
cin >> n ;
int x1 , x2 , y1 , y2 ;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n ; j ++)
{
cin >> a[i][j] ;
}
int f1 = 1 ;
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= n ; j ++)
{
if(a[i][j] == '*')
{
x1 = i ;
y1 = j ;
f1 = 0 ;
break;
}
}
if(f1 == 0) break;
}
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n ; j ++)
{
if(a[i][j] == '*')
{
x2 = i ;
y2 = j ;
}
}
if(x1 != x2 && y1 != y2)
{
a[x2][y1] = '*' ;
a[x1][y2] = '*' ;
}
else if(x1 == x2)
{
if(x1 + 1 <= n)
{
a[x1+1][y1] = '*' ;
a[x2+1][y2] = '*' ;
}
else
{
a[x1-1][y1] = '*' ;
a[x2-1][y2] = '*' ;
}
}
else if(y1 == y2)
{
if(y1 + 1 <= n)
{
a[x1][y1+1] = '*' ;
a[x2][y2+1] = '*' ;
}
else
{
a[x1][y1-1] = '*' ;
a[x2][y2-1] = '*' ;
}
}
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= n ; j ++)
{
cout << a[i][j] ;
}
cout << endl;
}
}
return 0 ;
}
第三题题意为给你一个只包含0和1和？的字符串，并且给你这个字符串中0和1的最大数量，问是否可以把？改成0或者1使之成为回文串，并且不超过给定的最大数量。
首先贪心来想，无非四种情况；
for(int i = 1 , j = n ; i < j ; i ++ , j – )
（1）如果i和j这个位置都是？的话，我们可以填0或者1
（2）如果i是0或1，j是？的话，那么j这个位置一定要填对应的0或1
（3）如果i是？的话，j是0或1，那么i这个位置一定要填对应的0或1
（4）如果i和j相等并且等于0或1
所以我们设2个变量s0和s1
在第二步第三步第四步分别统计出来s0和s1的数量
那么这个字符串只剩下了问号和已经匹配的0或1
那么我们接下来只需要模拟去把问号填完即可
for(int i = 1 , j = n ; i < j ; i ++ , j --)
{
if(s[i] == '?' && s[j] == '?')
{
if(a0 - s0 >= 2)
{
s[i] = '0' ;
s[j] = '0' ;
s0 += 2 ;
}
else if(a1 - s1 >= 2)
{
s[i] = '1' ;
s[j] = '1' ;
s1 += 2 ;
}
}
}
当n为奇数的情况下要特殊判断
所以最终代码如下
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N = 2e5 + 10 ;
typedef long long ll ;
int t , a0 , a1 ;
int n ;
char s[N] ;
int main()
{
cin >> t ;
while(t--)
{
cin >> a0 >> a1 ;
cin >> s + 1 ;
int s0 = 0 , s1 = 0 ;
int n = strlen(s + 1) ;
for(int i = 1 , j = n ; i < j ; i ++ , j --)
{
if(s[i] == '?' && s[j] == '?') continue ;
if(s[i] == s[j])
{
if(s[i] == '0')
{
s0 += 2 ;
}
else
{
s1 += 2 ;
}
}
else if((s[i] == '0' || s[i] == '1') && s[j] == '?')
{
s[j] = s[i] ;
if(s[i] == '0')
{
s0 += 2 ;
}
else
{
s1 += 2 ;
}
}
else if((s[j] == '0' || s[j] == '1') && s[i] == '?')
{
s[i] = s[j] ;
if(s[i] == '0')
{
s0 += 2 ;
}
else
{
s1 += 2 ;
}
}
}
for(int i = 1 , j = n ; i < j ; i ++ , j --)
{
if(s[i] == '?' && s[j] == '?')
{
if(a0 - s0 >= 2)
{
s[i] = '0' ;
s[j] = '0' ;
s0 += 2 ;
}
else if(a1 - s1 >= 2)
{
s[i] = '1' ;
s[j] = '1' ;
s1 += 2 ;
}
}
}
int sum0 = a0 - s0 ;
int sum1 = a1 - s1 ;
if(n & 1)
{
if(s[n/2 + 1] == '0') sum0 -= 1 ;
else if(s[n/2 + 1] == '1') sum1 -= 1 ;
if(sum0 == 1 && s[n/2 + 1] == '?')
{
s[n/2 + 1] = '0' ;
sum0 -= 1 ;
}
else if(sum1 == 1 && s[n/2 + 1] == '?')
{
s[n/2 + 1] = '1' ;
sum1 -= 1 ;
}
}
if(sum0 == 0 && sum1 == 0) cout << s + 1 << endl;
else puts("-1");
}
}
d题的题意为
删掉一个数并且选择一个数 是否有剩下的数之和等于选择的数
首先看n的大小是2e5,所以暴力n2会超时
那么考虑一下剩下的数之和一定是n项之和
我们可以先预处理前n+2项的和sum
首先对于选择的数,可以
sum - 选择的数g[i] o1处理
然后考虑删除
sum - g[x] = g[i]
很明显排序之后
g[x]具有单调性 sum和g[i]都为常数
所以可以用二分来做
所以总体时间复杂度为nlogn
代码如下
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, m;
int g[N];
LL s[N];
int main()
{
int T;
cin >> T;
while (T -- )
{
map<int, int> q;
cin >> n;
for (int i = 1; i <= n + 2; i ++ )
{
cin >> g[i];
s[i] = s[i - 1] + (LL)g[i];
q[g[i]] ++ ;
}
sort(g + 1, g + n + 3);
bool flag = true;
for (int i = 1; i <= n + 2; i ++ )
{
LL sum = s[n + 2] - g[i];
int l = 1, r = n + 2;
while (l < r)
{
int mid = l + r >> 1;
if (sum - g[mid] > g[i]) l = mid + 1;
else r = mid;
}
if (l == i)
{
if (q.count(g[i]) > 1) l ++ ;
else continue;
}
if (sum - g[l] == g[i])
{
for (int j = 1; j <= n + 2; j ++ )
if (i != j && j != l)
cout << g[j] << ' ';
cout << endl;
flag = false;
break;
}
}
if (flag) cout << "-1" << endl;
}
return 0;
}
