比赛链接：
SDNU ACM-ICPC 2019 Training Weekly Contest 1
题目链接：
A - Concatenated Multiples
题目大意：
给 n 个数，将这 n 个数两两组合，问有多少组可以被 k 整除.
分析：
比如 a 与 b 组合，则组合后为 
所以想要被整除只需要 （
所以用 map[i][j] 来表示 
之后 ans += 每个数对应前缀数 % k 的次数.
注意要特判一下 a 与 a 连接后的数是否为 k 的倍数.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int a[(int)1e5 * 2 + 10];
map <int, ll> mp[15];
int main()
{
int n, k;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
ll x = a[i];
for(int j = 1; j <= 10; ++j)
{
x *= 10;
x %= k;
mp[j][x]++;
}
}
ll ans = 0;
for(int i = 0; i < n; ++i)
{
ll x = a[i] % k;
int len = log10(a[i]) + 1;
ans += mp[len][(k - x % k) % k];
for(int j = 0; j < len; ++j)
x = x * 10 % k;
if((x + a[i] % k) % k == 0)
ans--;
}
printf("%lld\n", ans);
return 0;
}
题目链接：
B - Creating the Contest
题目大意：
给 n 个数字，呈递增序列，现让你确定满足连续且 
分析：
贪心，遇到不满足条件的断开即可，取最大长度.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
ll a[(int)1e5 * 2 + 10];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%lld", &a[i]);
int ans = 1;
int cnt = 1;
for(int i = 1; i < n; ++i)
{
if(a[i - 1] * 2 >= a[i])
cnt++;
else
cnt = 1;
ans = max(ans, cnt);
}
printf("%d\n", ans);
return 0;
}
题目链接：
C - Inventory
题目大意：
给 n 个数，输出一个新的排列，用最少次数的替换使新排列的数为 1 ~ n 的排列(顺序不固定).
分析：
水题，直接做.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e5 + 10;
int a[M];
bool vis[M];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
if(a[i] <= n)
vis[a[i]] = 1;
}
queue <int> q;
for(int i = 1; i <= n; ++i)
{
if(!vis[i])
q.push(i);
}
for(int i = 0; i < n; ++i)
{
if(vis[a[i]])
{
vis[a[i]] = 0;
continue;
}
a[i] = q.front();
q.pop();
}
for(int i = 0; i < n; ++i)
printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
return 0;
}
题目链接：
D - Many Equal Substrings
题目大意：
给定一个字符串， 以最小长度拼接 k 次，要求输出拼接后的字符串.
分析：
n 最大才 50，直接暴力求重合长度再相应输出即可.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
string s;
int f()
{
int len = s.size();
for(int i = 1; i < len; ++i)
{
if(s.substr(i) == s.substr(0, len - i))
return len - i;
}
return 0;
}
int main()
{
int n, k;
scanf("%d %d", &n, &k);
cin >> s;
int len = f();
cout << s;
for(int i = 1; i < k; ++i)
cout << s.substr(len);
cout << "\n";
return 0;
}
题目链接：
E - Maximal Intersection
题目大意：
给定 n 个区间，现让你移走一个区间，求剩余区间交集的最大值.
分析：
用两个 multiset 分别存左右区间端点，然后枚举移走的区间.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
struct node
{
int l;
int r;
};
struct node s[(int)1e5 * 3 + 10];
multiset <int> l, r;
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
{
scanf("%d %d", &s[i].l, &s[i].r);
l.insert(s[i].l);
r.insert(s[i].r);
}
int ans = 0;
for(int i = 0; i < n; ++i)
{
l.erase(l.find(s[i].l));
r.erase(r.find(s[i].r));
ans = max(ans, *r.begin() - *l.rbegin());
l.insert(s[i].l);
r.insert(s[i].r);
}
printf("%d\n", ans);
return 0;
}
题目链接：
F - Multicolored Markers
题目大意：
有 a 个红格子，b 个蓝格子，要求用这 a + b 个格子围成一个矩形，且至少有一种颜色的格子为矩形.
求大矩形周长的最小值.
分析：
枚举大矩形最短的边，再检查是否可行.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
bool check(ll a, ll b, ll x, ll y)
{
for(ll i = x; i >= 1; --i)
{
if(a % i == 0 && a / i <= y)
return 1;
if(b % i == 0 && b / i <= y)
return 1;
}
return 0;
}
int main()
{
ll a, b;
scanf("%lld %lld", &a, &b);
ll sum = a + b;
ll ans = 2 * (a + b) + 10;
for(ll i = 1; i * i <= sum; ++i)
{
if(sum % i)
continue;
ll x = i;
ll y = sum / x;
if(check(a, b, x, y))
ans = min(ans, 2 * (x + y));
}
printf("%lld\n", ans);
return 0;
}
题目链接：
G - Music
题目大意：
给定 T，S，q，求这首歌播放的次数.
T：音乐的总时长
S：预先下载好的时长
q：q 秒钟能够下载 q - 1 秒的音乐
分析：
追击相遇问题.
设在 t 时刻，音乐播放到未下载的部分.
则
解得 t == sq.
然后重复这个过程直到音乐全部播放完.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int main()
{
int T, s, q;
scanf("%d %d %d", &T, &s, &q);
int t = 1;
int cnt = 1;
while(1)
{
t = s * q;
s = t;
if(t >= T)
{
printf("%d\n", cnt);
break;
}
cnt++;
}
return 0;
}
题目链接：
H - Primes or Palindromes?
题目大意：
rub(n) ：不大于 n 回文数的个数(这里规定 0 不是回文数，由于没看清一直在 WA ).
给定整数 p 和 q，求满足 
分析：
回文数一开始用 stringstream 结果超时，后来才发现直接暴力就可以.
最后枚举 n 就可以.
注意最后要加上 long long.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e7 + 10;
int prime[M];
bool vis[M];
int num1[M];
int num2[M];
void init1()
{
int len = 0;
for(int i = 2; i < M; ++i)
{
if(!vis[i])
prime[len++] = i;
for(int j = 0; j < len && i * prime[j] < M; ++j)
{
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
for(int i = 2; i < M; ++i)
num1[i] = num1[i - 1] + !vis[i];
}
bool is(int n)
{
int m = n;
int sum = 0;
while(m)
{
sum *= 10;
sum += m % 10;
m /= 10;
}
return sum == n;
}
void init2()
{
for(int i = 1; i < M; ++i)
num2[i] = num2[i - 1] + is(i);
}
int main()
{
init1();
init2();
int p, q;
scanf("%d %d", &p, &q);
for(int i = M - 1; i >= 0; --i)
{
if((ll)num2[i] * p >= (ll)num1[i] * q)
{
printf("%d\n", i);
break;
}
}
return 0;
}
题目链接：
J - Tree with Small Distances
题目大意：
有一棵树，可以连接相应节点，要求每个节点与第 1 个节点的距离小于等于 2，求最少连线数.
分析：
贪心，如果 dis[i] > 2 的话，肯定是连接 father[i] 更实惠.
其实就是个无向图图，直接存.
然后 dfs 求每个节点的 dis，这时要特判一下 t 的子节点不能为 t 的父节点.
随后将 dis ＞ 2 的节点存到优先队列里（方便按 dis 排序）
接着更新就可以了，记得要把第 i 个节点的周围节点都更新.
代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e5 * 2 + 10;
vector <int> v[M];
int father[M];
int dis[M];
bool vis[M];
struct node
{
int num;
int len;
};
bool operator < (node a, node b)
{
return a.len < b.len;
}
void dfs(int now, int fa)
{
int len = v[now].size();
for(int i = 0; i < len; ++i)
{
int t = v[now][i];
if(t == fa)
continue;
dis[t] = dis[now] + 1;
father[t] = now;
dfs(t, now);
}
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i < n; ++i)
{
int a, b;
scanf("%d %d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1, 0);
priority_queue <node> q;
for(int i = 1; i <= n; ++i)
{
if(dis[i] > 2)
{
struct node t;
t.num = i;
t.len = dis[i];
q.push(t);
}
}
int ans = 0;
while(!q.empty())
{
int t = q.top().num;
q.pop();
if(vis[t])
continue;
int u = father[t];
vis[u] = 1;
ans++;
int len = v[u].size();
for(int i = 0; i < len; ++i)
vis[v[u][i]] = 1;
}
printf("%d\n", ans);
return 0;
}
京公网安备 11010502036488号