CF1520
\(div3\) 信心场!
Do Not Be Distracted!
开一个 \(vis\) 数组即可 只要连续两个字符不相同 就将前一个打上标记 那么我们访问任意一个具有标记的节点就判断无解即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
const int N = 128 + 5;
const int inf = 0x3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , vis[N];
string s;
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
int flag = 1;
memset ( vis , 0 , sizeof vis );
n = read();
cin >> s , s = " " + s;
for ( int i = 1 ; i <= n ; i ++ )
{
if ( vis[s[i]] ) { flag = 0; break; }
if ( s[i] != s[i+1] ) vis[s[i]] = 1;
}
cout << ( flag ? "YES" : "NO" ) << endl;
}
return 0;
}
Ordinary Numbers
模拟即可 对于 \(n< 10\) 进行 特判 其余情况将 \(i\) 从 \(11\) 开始枚举 依次遍历每一个普通数即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
const int N = 128 + 5;
const int inf = 0x3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , vis[N];
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
int cnt = 0;
n = read();
if ( n < 10 ) cout << n << endl;
else
{
int i = 11;
while ( 1 )
{
int base = i;
for ( int j = 1 ; j < 10 ; j ++ )
{
i = base * j;
// cout << i << endl;
++ cnt;
if ( i > n ) break;
}
if ( i > n ) break;
i = base * 10 + 1;
}
cout << cnt - 1 + 9 << endl;
}
}
return 0;
}
Not Adjacent Matrix
考虑连续的奇数和连续的偶数一定合法 那么我们从上到下从左到右地先将奇数填进去 再填写偶数
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
const int N = 128 + 5;
const int inf = 0x3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , a[N][N];
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
n = read();
if ( n == 1 ) { cout << 1 << endl; continue; }
if ( n == 2 ) { cout << -1 << endl; continue; }
int cnt = 1;
for ( int i = 1 ; i <= n ; i ++ )
for ( int j = 1 ; j <= n ; j ++ )
{
a[i][j] = cnt;
cnt += 2;
if ( cnt > n * n ) cnt = 2;
}
for ( int i = 1 ; i <= n ; i ++ , cout.put(endl) )
for ( int j = 1 ; j <= n ; j ++ )
cout << a[i][j] << ' ';
}
return 0;
}
Same Differences
推一下柿子可以发现 合法的统计当且仅当 \(a_j-j=a_i-i\) 那么开一个 \(map\) 从前到后扫一遍并统计即可
注意 \(long\ long\) 和数组大小()
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
#define int long long
const int N = 2e5 + 5;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , a[N];
map<int,int> mp;
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
int ans = 0;
n = read();
mp.clear();
for ( int i = 1 ; i <= n ; i ++ )
{
a[i] = read();
ans += mp[a[i]-i];
mp[a[i]-i] += 1;
}
cout << ans << endl;
}
return 0;
}
Arranging The Sheep
手推一下可以发现将东西合并到中间是最优的
那么对于奇数个 直接向中间靠拢 偶数个的话我们钦定一个中间点 让 \(tot/2\) 移动到这个位置并让其他所有星号移动到它两边即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
#define int long long
const int N = 1e6 + 5;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , cnt[N] , tot;
string s;
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
n = read() , tot = 0;
cin >> s , s = " " + s;
for ( int i = 1 ; i <= n ; i ++ ) if ( s[i] == '*' ) cnt[++tot] = i;
// for ( int i = 1 ; i <= tot ; i ++ ) cout << cnt[i] << ' ' ;
// cout << endl;
int ans = 0;
if ( tot & 1 )
{
int mid = tot / 2 + 1;
for ( int i = 1 ; i <= tot ; i ++ ) ans += abs ( cnt[i] - cnt[mid] ) - abs ( mid - i );
}
else
{
int mid = ( cnt[tot/2] + cnt[tot/2+1] ) / 2;//中间位置
for ( int i = 1 ; i <= tot ; i ++ ) ans += abs ( cnt[i] - mid ) - abs ( i - tot / 2 );
}
cout << ans << endl;
}
return 0;
}
Guess the K-th Zero (Easy version)
直接跟交互库二分即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
#define int long long
const int N = 1e6 + 5;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int T , n , k;
int query ( int r )
{
cout << "? " << 1 << ' ' << r << endl << flush;
return read();
}
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read() , T = read();
while ( T -- )
{
k = read();
int l = 1 , r = n;
while ( l <= r )
{
if ( ( mid - query ( mid ) ) < k ) l = mid + 1;
else r = mid - 1;
}
cout << "! " << l << endl << flush;
}
return 0;
}
Guess the K-th Zero (Hard version)
和上一个思路类似 我们还是尝试二分 但是采用记忆化的方法来减少询问次数
我们用一个差分树状数组来维护前缀和 如果我们
同时我们需要在每一次问出答案之后修改后面的前缀和
特别注意 我们在 \(upd\) 的时候 是修改而不是累加 所以需要将之前加上的前缀和贡献清理掉
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
#define int long long
const int N = 1e6 + 5;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int TT , n , k , res , vis[N];
int query ( int r )
{
cout << "? " << 1 << ' ' << r << endl << flush;
return read();
}
struct Tree
{
int t[N];
inl int lowbit ( int x ) { return x & -x; }
void upd ( int x , int val ) { for ( ; x <= n ; x += lowbit(x) ) t[x] += val; }
int query ( int x ) { int res = 0; for ( ; x ; x -= lowbit(x) ) res += t[x]; return res; }
}T;
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read() , TT = read();
while ( TT -- )
{
k = read();
int l = 1 , r = n;
while ( l <= r )
{
if ( vis[mid] ) res = T.query(mid);
else res = query(mid) , T.upd(mid+1,-res+T.query(mid)) , T.upd(mid,res-T.query(mid)) , vis[mid] = 1;
if ( ( mid - res ) < k ) l = mid + 1;
else r = mid - 1;
}
cout << "! " << l << endl << flush;
T.upd ( l , 1 );
}
return 0;
}
//10100
/*
5 3
1
2
1
1
2
3
3
1
*/
To Go Or Not To Go?
显然只会使用一次传送门 反证: 如果我们使用 \(a\rightarrow b\) 和 $c\rightarrow d $ 一定不如 \(a\rightarrow d\)
然后我们需要从终点和起点进行 \(bfs\) 统计 \(dis[i][j]+a[i][j]\) 的最小值 这样两个加和就是答案了 最后再和不使用传送的答案取 \(min\) 即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
#define int long long
const int dx[4] = { 0 , 1 , 0 , -1 };
const int dy[4] = { 1 , 0 , -1 , 0 };
const int N = 2e3 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , m , w , anss = inf , ans1 = inf , ans2 = inf , a[N][N] , dis[N][N];
struct node { int x , y; };
int check ( int x , int y ) { return 1 <= x && x <= n && 1 <= y && y <= m && a[x][y] != -1; }
void bfs ( int sx , int sy , int &ans )
{
queue<node> q;
memset ( dis , -1 , sizeof dis );
if ( a[sx][sy] != -1 ) dis[sx][sy] = 0 , q.push ( { sx , sy } );
while ( !q.empty() )
{
int x = q.front().x , y = q.front().y; q.pop();
for ( int i = 0 ; i < 4 ; i ++ )
{
int tx = x + dx[i] , ty = y + dy[i];
if ( check(tx,ty) && dis[tx][ty] == -1 )
{
dis[tx][ty] = dis[x][y] + 1;
q.push ( { tx , ty } );
}
}
}
if ( sx == 1 && dis[n][m] != -1 ) anss = min ( anss , dis[n][m] * w );
for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= m ; j ++ ) if ( dis[i][j] != -1 && a[i][j] > 0 ) ans = min ( ans , dis[i][j] * w + a[i][j] );
}
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read() , m = read() , w = read();
for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= m ; j ++ ) a[i][j] = read();
bfs ( 1 , 1 , ans1 );
bfs ( n , m , ans2 );
anss = min ( anss , ans1 + ans2 );
cout << ( anss == inf ? -1 : anss ) << endl;
return 0;
}