Codeforces Round #719 (Div. 3)A-E个人题解
A.Do Not Be Distracted!
链接
https://codeforces.com/contest/1520/problem/A
题目大意
给定一段仅由26个字母组成的字符串，问对于这段字符串，每个字母是否只出现一次。（一段相同字母代表出现一次）
思路
用map记录每个相同字母的位置，每次计算当前字母的位置与上一次出现的位置的差值，差值不等于1的话则意味着出现了两次。
#include
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 30;
map pre;
int main(void){
IOS;
int t;
cin>>t;
while( t-- ){
int n;
string str;
cin >> n >> str;
pre.clear();
bool is_yes = true;
for( int i = 0 ; i < n ; i++ ){
if( pre[str[i]] == 0 ){
pre[str[i]] = i+1;
}
else if( i + 1 - pre[str[i]] != 1 ){
is_yes = false;
break;
}
else pre[str[i]] = i+1;
}
if( is_yes ) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
B. Ordinary Numbers
链接
https://codeforces.com/contest/1520/problem/B
题目大意
我们称11，22，33，这些由单一数字组成的为普通数字，现给出一个n，询问其中普通数字个数。
思路
1-9中有9个普通数字，10-99中有9个普通数字，每次倍增10倍，普通数字总数+9，而不满十倍关系的时候，观察第二位数是否比第一位数大，若大，必包含当前最高位的普通数字，若小，则不包含当前最高位的普通数字，例如7860包含7777，7680不包含7777。如此，对于任意n，我们可以求出理想状况下应满足的理想数目，再判断是否能够达到最高位的普通数字，若不能，理想数目-1即可。
#include
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
int num[30];
LL solve( LL n ){
if( n < 10 ) return n;
LL bit = 0, m = n, ans = 0;
while( m ){
num[++bit] = m % 10;
m /= 10;
}
ans = (bit-1)*9 + num[bit]; //次一位的全部普通数字+最高位包含的普通数字。
for( int i = bit-1; i >= 1 ; i -- ){
if( num[i] > num[bit] ) break;
if( num[i] < num[bit] ){
ans--;
break;
}
}
return ans;
}
int main(void){
IOS;
int t;
cin>>t;
while( t-- ){
LL n;
cin>>n;
cout << solve(n) << endl;
}
return 0;
}
C. Not Adjacent Matrix
链接
https://codeforces.com/contest/1520/problem/C
题目大意
给一个整数n，让你构造一个n*n的矩阵，里面任意元素之间差值的绝对值不等于1，每个元素都必须是1到n2之间的数字，且只能出现一次。问是否能够构造成功，可以则输出矩阵，不可以则输出-1；
思路
将每个元素分为奇偶两组，先填充奇数组，填充满了再填充偶数组。
代码
#include
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 110, M = 10000;
int g[N][N],a[M],b[M],cnt1,cnt2;
void inti(){
for( int i = 1 ; i <= N*N ; i++ ){
if( i % 2 == 1 ) a[++cnt1] = i;
else b[++cnt2] = i;
}
}
int main(void){
IOS;
int t;
cin>>t;
inti();//初始化先筛一遍
while( t-- ){
int n;
cin >> n;
if( n == 1 || n == 2 ){ cout << (n == 1 ? 1 : -1) << endl; continue ;}
// n == 2 时候为1，2，3，4，无论如何放置，都必定存在差值绝对值为1的情况
memset(g,0,sizeof g);
bool is_yes = true;
int step = 1;
for( int i = 1 ; i <= n ; i++ )
for( int j = 1 ; j <= n ; j++ ){
if( a[step] > n*n ){//奇数部分完毕，初始化step和更新分支条件
is_yes = false;
step = 1;
}
if( is_yes ) g[i][j] = a[step++];
else g[i][j] = b[step++];
}
for( int i = 1 ; i <= n ; i++ )
for( int j = 1 ; j <= n ; j++ )
if( j == n ) cout << g[i][j] << endl;
else cout << g[i][j] << " ";
}
return 0;
}
D. Same Differences
链接
https://codeforces.com/contest/1520/problem/D
题目大意
给你一个有n个元素的数组，询问有多少对（i，j）满足以下条件
\[i思路
对条件进行恒等变式，就可以化成a[j] - j == a[i] - i，用map存一下每个元素减去下标的值即可，当第二次出现时候进行计算。
代码
#include
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 2*1e5+10;
typedef long long LL;
unordered_map a;
int main(void){
IOS;
int t;
cin >> t;
while( t-- ){
int n;
cin >> n;
a.clear();
LL ans = 0;
for( int i = 1 ; i <= n ; i++ ){
int x;
cin >> x;
if( a[x-i] ) ans += a[x-i];
a[x-i]++;
}
cout << ans << endl;
}
return 0;
}
E. Arranging The Sheep
链接
https://codeforces.com/contest/1520/problem/E
题目大意
给你一个只包含‘*’和‘.’的字符串,前者代表羊，后者代表空地，询问所有羊合并到一堆的最小步数。
思路
一个数轴上有n个点，找出一个点使所有点到这个点的距离之和尽量小，这些点的中位数就是目标点。那么这道题就变成了求所有点到中位点的距离。
也可以利用前缀和后缀数组解决，遍历两边，求出每一点左右两堆羊到此的步数之和，再遍历一遍所有空点，取出步数之和的最小值。
代码
//解法1---中位数
#include
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e6+10, INF = 0x3f3f3f3f;
int dis[N];
int main(void){
IOS;
int t;
cin>>t;
while( t-- ){
int n;
cin>>n;
string str;
cin>>str;
int cnt = 0;
for( int i = 0 ; i < n ; i++ )
if( str[i] == '*' ) dis[cnt++] = i+1;
int mid = cnt/2, mi = 0;
mi = dis[mid];
long long ans = 0;
for( int i = 0 ; i < cnt ; i++ )
ans += abs(dis[i]-mi) - abs(mid-i);
cout << ans << endl;
}
return 0;
}
//解法2--前后缀
#include
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
const int N = 1e6+10;
const LL LNF = 1e18;
LL pr[N],ne[N];
int main(void){
IOS;
int t;
cin >> t;
while( t-- ){
LL n;
string str;
cin >> n >> str;
//前缀计算
for( int i = 0 ; i < n ; i++ ){
ne[i] = 0;
pr[i] = 0;
}
LL cnt = 0;
for( LL i = 0 ; i < n ; i++ ){
if( i == 0 ){
pr[i] = 0;
cnt += ( str[i] == '*' );
continue;
}
if( str[i] == '*' ) pr[i] = pr[i-1],++cnt;
else pr[i] = pr[i-1] + cnt;
}
//后缀计算
cnt = (LL)0;
for( LL i = n-1 ; i >= 0 ; i-- ){
if( i == n-1 ){
ne[i] = 0;
cnt += ( str[i] == '*' );
continue;
}
if( str[i] == '*' ) cnt++,ne[i] = ne[i+1];
else ne[i] = ne[i+1] + cnt;
}
//求结果
LL ans = LNF;
for( LL i = 0 ; i < n ; i++ ){
if( str[i] == '.' ){
if( i > 0 ) ans = min(pr[i-1]+ne[i],ans);
if( i < n-1 ) ans = min(ne[i+1]+pr[i],ans);
}
}
cout << ( ans == LNF ? 0 : ans ) << endl;
}
return 0;
}