题意
给你两个数x , y ,输出两个整数a b使得x * b^a = y,如果不存在a,b输出0 0
inline void solve() {
int x , y;
cin >> x >> y;
int d = gcd(x , y);
int k1 = x / d , k2 = y / d;
if (x * (k2 / k1) == y) cout << 1 << ' ' << k2 / k1 << endl;
else cout << 0 << ' ' << 0 << endl;
}
由题意可以知y一定是x的倍数,如果(y % x != 0) 输出-1,否则输出1 y / x.
题意
求出ab - zy所代表的权值
inline void solve() {
string s;
cin >> s;
int x = s[0] - 'a' + 1 , y = s[1] - 'a' + 1;
if (y < x) cout << (x - 1) * 26 + y - (x - 1) << endl;
else cout << (x - 1) * 26 + y - x << endl;
}
两种解决方案 : 1 推公式
2 模拟过程,两层for [a - z] if (i == j) continue 否则 idx ++
题意
给你一个只包含字符’a’的主串s,和一个字符串t,对于主串中的字符’a’都可以被字符串t替换,输出有多个不同的字符串。
LL power(LL a , LL b) {
LL res = 1;
for (int i = 1; i <= b; i ++ ) res *= a;
return res;
}
inline void solve() {
string s , t;
cin >> s >> t;
if (t[0] == 'a' && t.size() == 1) cout << 1 << endl;
else {
bool flag = false;
for (int i = 0 ; i < t.size() ; i ++ )
if (t[i] == 'a')
flag = true;
LL ans = power((LL)2 , (LL)s.size());
if (flag) cout << -1 << endl;
else cout << ans << endl;
}
}
分三种情况 :
1 如果字符串t只包含一个’a’ 输出1
2 如果字符串t里面包含a和其他的字符 输出 -1
3 如果字符串t里面不包含a 输出2^s.size() (字符串s的每一个位置都可以被t替换所以有2的幂次方种方案)
题意
有三个数组a , b , c,刚开始的时候只有数组a有值,a 可以对b进行操作 : 对于数组a可以取出最后一个数字放到b的中间,如果b的个数奇数则可以放在a[mid - 1] 或者 a[mid + 1]
对于数字b可以对数字c进行操作 : 每次从b的中间取放到c的末尾(如果b的个数奇数则可以取b[mid - 1] 或者 b[mid + 1]),通过这些操作判断c是否可以排好序,如果可以输出YES , 否则NO
inline void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
if (n % 2) {
for (int i = 1; i < n - 1; i += 2)
if (a[i] > a[i + 1])
swap(a[i] , a[i + 1]);
}
else {
for (int i = 0; i < n - 1; i += 2)
if (a[i] > a[i + 1])
swap(a[i] , a[i + 1]);
}
for (int i = 1; i < n; i ++ )
if (a[i - 1] > a[i]) {
cout << "NO" << endl;
return ;
}
cout << "YES" << endl;
}
观察a , b 之间的关系a[n - 1] , a[n] 会放在 b[1] 或者 b[n] , 观察b , c之间的关系b[1] , b[n] 会放在 c[n - 1] , c[n] , 综上a[n - 1] , a[n] 会放在c[n - 1] 或者 c[n] ==>数组c == 数组a两两一对可以互换位置,最后判断一下是否是顺序。
题意
给你一个数组a[1 - n],有一个操作 : a[i] - 2 , a[i - 1] - 1 , a[i + 1] - 1 , 输出使两个a[i] = 0 的最小操作数。
inline void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
int ans = inf;
if (n == 1) {
a[1] ++ ;
cout << a[1] / 2 << endl;
return ;
}
else {
// 破坏连续的两堵墙
for (int i = 2; i <= n; i ++ ) {
int maxv = max(a[i] , a[i - 1]);
int minv = min(a[i] , a[i - 1]);
if (maxv > minv * 2) {
ans = min(ans , (maxv + 1) / 2);
continue;
}
int t = (a[i] + a[i - 1]) / 3;
if ((a[i] + a[i - 1]) % 3 != 0) t ++ ;
ans = min(ans , t);
}
// 破坏间隔的墙
for (int i = 2; i <= n - 1; i ++ ) {
int t = (abs(a[i - 1] - a[i + 1]) + 1) / 2;
ans = min(ans , min(a[i - 1] , a[i + 1]) + t);
}
// 破坏最小的墙
sort(a + 1 , a + 1 + n);
a[1] ++ ;
a[2] ++ ;
ans = min(ans , a[1] / 2 + a[2] / 2);
cout << ans << endl;
}
}
分为4种情况
1 只有一堵墙
2 破坏连续的两堵墙
3 破坏间隔的墙 (例如a[i - 1] 和 a[i + 1])
4 破坏最小的墙
题意
给出一个nm矩阵图,其中表示图标,.表示空,然后给出q个询问,x , y表示把该点的图标删除,问把剩余的图标按win图标那样排列最少需要移动多少个图标。(win图标排列 : 先按列排,如果列排满了,就重启一列。)
int lowbit(int x) {
return x & -x;
}
int get(int x , int y) {
return x + (y - 1) * n;
}
void add(int x , int c) {
for (int i = x; i <= get(n , m); i += lowbit(i)) tr[i] += c;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
inline void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ) {
cin >> g[i][j];
if (g[i][j] == '*') add(get(i , j) , 1);
}
while (q -- ) {
int x , y;
cin >> x >> y;
if (g[x][y] == '*') {
g[x][y] = '.';
add(get(x , y) , -1);
}
else {
g[x][y] = '*';
add(get(x , y) , 1);
}
int sum = query(get(n , m));
cout << sum - query(sum) << endl;
}
}
先把矩阵转化成字符串,然后用树状数组处理每一个询问就可以了。