在B题上卡了一下，我是SB。
题意：
就问你有没有字母不是连续着出现
思路：
直接判断即可
string s;
int n;
int cnt[26];
int main(){
int T;
cin >> T;
while(T--)
{
memset(cnt, 0, sizeof cnt);
cin >> n;
cin >> s;
bool flag = true;
for(int i = 0 ; i < n ; i ++)
{
if(i && s[i - 1] != s[i])
if(cnt[s[i] - ‘A‘])
{
flag = false;
break;
}
cnt[s[i] - ‘A‘] ++;
}
if(flag) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
题意：问你从1到n要多少个数是数的每位数字都相等
思路：
直接枚举相同的数字是\(X_i\)，然后不断进行\(X_i = X_i * 10 + X_i\)操作，直到数字大于n，统计数目即可。
ll n, k;
int main(){
IOS;
int T;
cin >> T;
while(T--)
{
cin >> n;
ll ans = 0;
for(ll i = 1 ; i <= 9 ; i ++)
{
ll temp = 0;
while(temp * 10 + i <= n)
{
temp = temp * 10 + i;
ans ++;
}
}
cout << ans <<"\n";
}
return 0;
}
开始错误的代码
这个写法错在了特判最高位是否可行处
ll n;
vector<int> v;
int main(){
IOS;
int T;
cin >> T;
while(T--)
{
cin >> n;
while(n)
{
v.push_back(n % 10);
n /= 10;
}
reverse(v.begin(), v.end());
int ans = (v.size() - 1) * 9 + v[0] - 1;
bool flag = true;
int d = v[0];
for(auto x : v) //此处错了
if(x < d) flag = false;
if(flag) ans ++;
cout << ans << "\n";
v.clear();
}
return 0;
}
题意：让你将 n * n个数放进 n * n的矩阵里，使得相邻位置的数数值不相邻
思路：
按照顺序，先放奇数，再放偶数，最后判断是否合法即可。
int n;
int g[N][N];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool check(int a, int b)
{
int c = g[a][b];
for(int i = 0 ; i < 4 ; i ++)
{
int x = a + dx[i];
int y = b + dy[i];
if(x < 1 || x > n || y < 1 || y > n) continue;
if(abs(g[x][y] - c) == 1) return false;
}
return true;
}
int main(){
IOS;
int T;
cin >> T;
while(T--)
{
cin >> n;
int lim = n * n;
int l = 1, r = 2;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n ; j ++)
{
if(l <= lim) g[i][j] = l, l += 2;
else g[i][j] = r, r += 2;
}
bool flag = true;
for(int i = 1 ; i <= n ; i ++)
{
if(!flag) break;
for(int j = 1 ; j <= n ; j ++)
{
if(!check(i, j)) flag = false;
break;
}
}
if(!flag) cout << "-1\n";
else
{
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= n ; j ++)
cout << g[i][j] << ‘ ‘;
cout << ‘\n‘;
}
}
}
return 0;
}
题意：
给你一个序列，问你有多少序列满足\(i < j\)并且$ a_j - a_i = j - i $。
思路：
将式子变形，变成$ a_j - j = a_i - i $，就非常简单啦
int n;
int a[N];
map<ll, ll> mp;
int main(){
IOS;
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1 ; i <= n ; i ++)
{
cin >> a[i];
a[i] -= i;
mp[a[i]] ++;
}
ll ans = 0;
for(auto x : mp) ans += x.y * (x.y - 1) / 2;
cout << ans << "\n";
mp.clear();
}
return 0;
}
题意：给你一个字符串，里面有 . 和 * ，每次可以移动一个到.处，问你最少移动多少次可以让所有连续。
思路：
直接线性dp即可，因为你左边怎么凑过来的和右边怎么凑过来的无关，只需要求左边加右边最小即可。
int n;
string s;
pll l[N];
pll r[N];
int main(){
IOS;
int T;
cin >> T;
while(T--)
{
cin >> n >> s;
l[0].y = (s[0] == ‘*‘);
for(int i = 1 ; i < n ; i ++)
{
if(s[i] != ‘*‘)
{
l[i].x = l[i - 1].x + l[i - 1].y;
l[i].y = l[i - 1].y;
}
else l[i] = l[i - 1];
if(s[i] == ‘*‘)
l[i].y ++;
}
r[n - 1].y = (s[n - 1] == ‘*‘);
for(int i = n - 2 ; i >= 0 ; i --)
{
if(s[i] != ‘*‘)
{
r[i].x = r[i + 1].x + r[i + 1].y;
r[i].y = r[i + 1].y;
}
else r[i] = r[i + 1];
if(s[i] == ‘*‘)
r[i].y ++;
}
ll ans = 1e18;
for(int i = 0 ; i < n ; i ++)
ans = min(ans, l[i].x + r[i].x);
cout << ans << "\n";
for(int i = 0 ; i < n ; i ++)
l[i].x = l[i].y = r[i].x = r[i].y = 0;
}
return 0;
}
题意：
有一个隐藏的数组，只有0和1，让你每次查询一个区间，每次系统会返回区间的和，让你在20次查询内找到数组中的第k个0。
思路：
显然是二分，二分查找即可，详情看如下代码。
int n, t, k;
int sum;
int main(){
IOS;
cin >> n >> t;
cin >> k;
int l = 1, r = n;
while(l < r)
{
int mid = l + r >> 1;
cout << "? " << l << " " << mid << "\n";
cout.flush();
cin >> sum;
if(sum == 0)
{
cout << "! " << l + k - 1 << "\n";
cout.flush();
return 0;
}
if(sum + k <= mid - l + 1) r = mid;
else k -= (mid - l + 1 - sum), l = mid + 1;
}
cout << "! " << l << "\n";
cout.flush();
return 0;
}
题意：
相比F1加入了一条，每次查询到的0，在查询后会变成1，而原来数组中的0该是第几个现在还是第几个。
思路：
需要搞一个东西维护当前查询的0的偏移量，赛中没写出来后面再补。
后面再补
Codeforces Round #719 (Div. 3) 题解
原文：https://www.cnblogs.com/luoyicong/p/14733600.html