A A｜B
题目大意
给定两个正整数 ，统计满足以下条件的
的个数：
1.
2.
分析
说明
与
的二进制表示中
的位置互斥.
这里很***道地用了数位 dp（说好的 小白 呢？
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
int a, x;
int f[35];
int num[35];
int dfs(int pos, bool limit)
{
if(pos == -1) return 1;
if(!limit && ~f[pos]) return f[pos];
int up = (limit ? num[pos] : 1);
int res = 0;
for(int i = 0; i <= up; ++i)
{
if(i == 0 || i == 1 && !(a>>pos&1))
{
res += dfs(pos - 1, limit && (i == up));
}
}
if(!limit) f[pos] = res;
return res;
}
int dfs(int n)
{
int pos = 0;
while(n)
{
num[pos++] = n % 2;
n /= 2;
}
return dfs(pos - 1, 1);
}
void work()
{
memset(f, -1, sizeof(f));
scanf("%d %d", &a, &x);
printf("%d\n", dfs(x) - 1);
}
int main()
{
// freopen("input.txt", "r", stdin);
int T; scanf("%d", &T);
while(T--) work();
// work();
return 0;
} B A + B
题目大意
将数字以及加号用字符矩阵的形式进行表示，对应关系如下：
以字符形式给出一个运算式，请你计算结果，同时也请你将结果按照字符的形式输出
分析
直接模拟噢！
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = (int)1e3;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
string s[5];
map<string, int> mp;
map<int, string> remp;
void init()
{
string t;
t = "####.##.##.####";
assert(t.size() == 15);
mp[t] = 0;
t = "..#..#..#..#..#";
assert(t.size() == 15);
mp[t] = 1;
t = "###..#####..###";
assert(t.size() == 15);
mp[t] = 2;
t = "###..####..####";
assert(t.size() == 15);
mp[t] = 3;
t = "#.##.####..#..#";
assert(t.size() == 15);
mp[t] = 4;
t = "####..###..####";
assert(t.size() == 15);
mp[t] = 5;
t = "####..####.####";
assert(t.size() == 15);
mp[t] = 6;
t = "####.##.#..#..#";
assert(t.size() == 15);
mp[t] = 7;
t = "####.#####.####";
assert(t.size() == 15);
mp[t] = 8;
t = "####.####..####";
assert(t.size() == 15);
mp[t] = 9;
t = "....#.###.#....";
assert(t.size() == 15);
mp[t] = 10;
for(auto x: mp)
{
remp[x.second] = x.first;
}
// for(auto x: remp) cout << x.first << " " << x.second << "\n";
}
int cal(int m)
{
string t = "";
for(int i = 0; i < 5; ++i) t += s[i].substr(m, 3);
return mp[t];
}
stack<int> st;
string ans[5];
void drawNum(int n)
{
for(int i = 0; i < 5; ++i)
{
ans[i] += remp[n].substr(3 * i, 3);
}
}
void draw(int n)
{
for(int i = 0; i < 5; ++i) ans[i] = "";
if(n == 0) {drawNum(0); return;}
while(n)
{
st.push(n % 10);
n /= 10;
}
while(!st.empty())
{
drawNum(st.top());
st.pop();
if(!st.empty())
{
for(int i = 0; i < 5; ++i) ans[i] += ".";
}
}
for(int i = 0; i < 5; ++i) cout << ans[i] << "\n";
}
void work()
{
for(int i = 0; i < 5; ++i) cin >> s[i];
int ans = 0, len = s[0].size(), x = 0, f = 0;
for(int i = 0; i < len; i += 4)
{
f = cal(i);
if(f <= 9) x = x * 10 + f;
else if(f == 10)
{
ans += x;
x = 0;
}
}
ans += x;
draw(ans);
}
int main()
{
// freopen("input.txt", "r", stdin);
init();
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
for(int ca = 1; ca <= T; ++ca)
{
work();
if(ca < T) cout << "\n";
}
// work();
return 0;
} C 图像存储
题目大意
数字图像是一个由“0”和“1”这两个元素组成的矩阵，除去边角上的元素，每个元素都有上下左右相邻的四个元素。再一个数字图像中，元素“0”代表空白，只有元素“1”所在的位置才有一个黑点。由此，一副黑白的图像得以显现。
为了能在更少的空间里存储更多的图像，一个可行的办法就是每种相同的黑块只保留一个，其他的地方只保留位置，这样便实现了压缩。查看时，只需将保留的黑块拓印到其它的位置，这样就实现了图像的复原。
可见，该技术的关键就是对不同的黑块进行记录。我们把由若干个相邻的“1”构成的区域定义为黑块，规定一个孤立的“1”也是一个黑块，黑块中“1”的个数为黑块的大小，通过上下左右平移可以实现重合并且等大的黑块为同一种黑块。现在你的任务是分别算出一个图像中黑块的个数和种数。
分析
BFS + 哈希
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e3;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
int n, m;
char s[M + 5][M + 5];
int vis[M + 5][M + 5];
struct node
{
int x, y;
node(int _x = 0, int _y = 0): x(_x), y(_y){}
};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct node2
{
int n, m; ull h;
node2(int _n, int _m, ull _h): n(_n), m(_m), h(_h){}
bool operator< (const node2& b)const
{
if(n != b.n) return n < b.n;
if(m != b.m) return m < b.m;
return h < b.h;
}
bool operator== (const node2& b)const
{
return n == b.n && m == b.m && h == b.h;
}
};
vector<node2> Hash;
void bfs(int x, int y)
{
queue<node> q;
int xmin = x, ymin = y, xmax = x, ymax = y;
node u, v;
vis[x][y] = 1;
q.push(node(x, y));
while(!q.empty())
{
u = q.front(); q.pop();
xmin = min(xmin, u.x); ymin = min(ymin, u.y);
xmax = max(xmax, u.x); ymax = max(ymax, u.y);
for(int i = 0; i < 4; ++i)
{
v = u;
v.x += dx[i], v.y += dy[i];
if(v.x < 0 || v.x >= n || v.y < 0 || v.y >= m) continue;
if(vis[v.x][v.y] == 0 && s[v.x][v.y] == '1')
{
vis[v.x][v.y] = 1;
q.push(node(v.x, v.y));
}
}
}
ull h = 0;
for(int i = xmin; i <= xmax; ++i)
{
for(int j = ymin; j <= ymax; ++j)
{
if(vis[i][j] == 1)
{
vis[i][j] = 2;
h = h * 1331 + 1;
}
else h = h * 1331;
}
}
Hash.push_back(node2(xmax - xmin + 1, ymax - ymin + 1, h));
}
void work()
{
Hash.clear();
for(int i = 0; i < n; ++i)
{
scanf("%s", s[i]);
for(int j = 0; j < m; ++j)
{
vis[i][j] = 0;
}
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(vis[i][j] || s[i][j] == '0') continue;
bfs(i, j);
}
}
printf("%d ", Hash.size());
sort(Hash.begin(), Hash.end());
Hash.erase(unique(Hash.begin(), Hash.end()), Hash.end());
printf("%d\n", Hash.size());
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
while(~scanf("%d %d", &n, &m) && (n + m)) work();
// int T; scanf("%d", &T);
// while(T--) work();
// work();
return 0;
} D 坐标计数
题目大意
定义一个坐标变换，坐标 变换后变为
。
给定一片矩形区域，计算区域内有多少个整数点在经过有限次变换后变为 。
分析
手玩一下发现所有点都可以经过有限次变换后变为 .
那么用容斥原理计算一下矩形面积即可.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
ll cal(int x, int y)
{
return 1ll * x * y;
}
void work()
{
int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
ll ans = cal(x2, y2) - cal(x2, y1 - 1) - cal(x1 - 1, y2) + cal(x1 - 1, y1 - 1);
printf("%lld\n", ans);
}
int main()
{
// freopen("input.txt", "r", stdin);
int T; scanf("%d", &T);
while(T--) work();
// work();
return 0;
} E 解方程
题目大意
给出两个正整数 ，计算满足方程
的正整数
的组数。
分析
从 开始推
把 移项到等式右边得
.
即 .
要保证 为整数，只需让
.
因此答案即为 的约数个数.
记 唯一分解为
，则
的约数个数为
.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
bool is_prime[M + 5];
int prime[M + 5], cnt;
void init()
{
memset(is_prime, 1, sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int i = 2; i <= M; ++i)
{
if(is_prime[i])
{
prime[++cnt] = i;
}
for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
{
is_prime[i * prime[j]] = 0;
if(i % prime[j] == 0)
{
break;
}
}
}
}
unordered_map<ll, int> mp;
void divide(ll n)
{
mp.clear();
for(int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= n; ++i)
{
if(n % prime[i] == 0)
{
int c = 0;
while(n % prime[i] == 0)
{
n /= prime[i];
++c;
}
mp[prime[i]] = c;
}
}
if(n != 1) mp[n] = 1;
}
void work()
{
int a, b; scanf("%d %d", &a, &b);
divide(1ll * a * b);
int ans = 1;
for(auto x: mp) ans *= x.second + 1;
printf("%d\n", ans);
}
int main()
{
init();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int T; scanf("%d", &T);
while(T--) work();
// work();
return 0;
} F 消减整数
题目大意
给你一个数字 依序减掉
直到不够减。如果刚好减到
就结束，否则就加上
继续从
开始减，直到减到
为止。
请给出一个数字，计算对于该数字一共重复了几次这个过程。
分析
对于一次过程，可以用二分快速求出本次总共减去多少.
接着对答案加了个记忆化就艹过去了！
之后再来更正解吧~
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = (int)1e3;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
unordered_map<int, int> mp;
int cal(int n)
{
int l = 1, r = (int)1e5, mid;
while(l < r)
{
mid = (l + r + 1) >> 1;
if(1ll * mid * (mid + 1) / 2 <= n) l = mid;
else r = mid - 1;
}
return 1ll * r * (r + 1) / 2;
}
void work()
{
int n; scanf("%d", &n);
if(mp.count(n))
{
printf("%d\n", mp[n]);
return;
}
int m = n;
int p = 0;
while(1)
{
++p;
n -= cal(n);
if(n == 0)
{
mp[m] = p;
printf("%d\n", p);
return;
}
n += m;
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int T; scanf("%d", &T);
while(T--) work();
// work();
return 0;
} G 简单题的逆袭
题目大意
给定 ，找出满足方程
的最大的
.
分析
一开始尝试分类讨论来着，结果一直 WA 个不停...
于是采用了暴力.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
ll read()
{
ll x = 0; int f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void work()
{
ll x, y;
x = read(), y = read();
int k = 0;
ll t = 1;
if(t > y)
{
printf("-1\n");
return;
}
for(int i = 1; i <= 70; ++i)
{
if(t <= y && t * x > y)
{
printf("%d\n", i - 1);
return;
}
t *= x;
}
printf("-1\n");
}
int main()
{
// freopen("input.txt", "r", stdin);
int T; scanf("%d", &T);
while(T--) work();
// work();
return 0;
} H 对称之美
题目大意
给出 个字符串，从第
个字符串一直到第
个字符串每个串取一个字母来构成一个新字符串，新字符串的第
个字母只能从第i行的字符串中选出，这样就得到了一个新的长度为
的字符串，请问这个字符串是否有可能为回文字符串？
分析
统计每个串的每个字母的出现情况，然后暴力匹配.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = (int)1e2;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
int n, cnt[M + 5][26];
char s[M + 5];
void work()
{
scanf("%d", &n);
for(int i = 0; i < n; ++i)
{
scanf("%s", s);
int m = strlen(s);
for(int j = 0; j < 26; ++j) cnt[i][j] = 0;
for(int j = 0; j < m; ++j) cnt[i][s[j] - 'a']++;
}
for(int i = 0; i < n / 2; ++i)
{
bool f = 0;
for(int j = 0; j < 26; ++j)
{
if(cnt[i][j] && cnt[n - i - 1][j])
{
f = 1;
break;
}
}
if(!f)
{
puts("No");
return;
}
}
puts("Yes");
}
int main()
{
// freopen("input.txt", "r", stdin);
int T; scanf("%d", &T);
while(T--) work();
// work();
return 0;
} I 非对称之美
题目大意
给出一个字符串，求最长非回文子字符串的长度
分析
如果一个串 不是回文串，那么答案就是
.
否则如果 不是回文串，那么答案就是
.
否则不难证明串 的所有字符全部相同，答案为
.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = (int)1e7;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;
int n;
char s[M + 5];
bool check()
{
for(int i = 0; i < n / 2; ++i)
{
if(s[i] != s[n - i - 1]) return 0;
}
return 1;
}
void work()
{
scanf("%s", s);
n = strlen(s);
if(check())
{
--n;
if(check()) printf("%d\n", 0);
else printf("%d\n", n);
}
else printf("%d\n", n);
}
int main()
{
// freopen("input.txt", "r", stdin);
// int T; scanf("%d", &T);
// while(T--) work();
work();
return 0;
} 
京公网安备 11010502036488号