智算之道2020复赛题解
程序员文章站
2022-07-08 10:14:35
A数字思路: 直接暴力枚举就好了#include#include#include
A数字
思路: 直接暴力枚举就好了
#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>
using namespace std;
typedef long long ll;
int get(ll x) {
if(x == 0) return 1;
int cnt = 0;
while(x) {
cnt++;
x /= 10;
}
return cnt;
}
int main() {
ll a,b;scanf("%lld%lld",&a,&b);
ll ans = 0;
int cnt = get(a);
ll num = 1;
for(int i = 1;i <= cnt;i++) {
num = num * 10;
}
for(ll i = 1;i <= 9;i++) {
for(ll j = 0;j <= 9;j++) {
for(ll k = 0;k <= 9;k++) {
ll now = (i * 100 + j * 10 + k) * num + a;
if(now % b == 0) {
ans++;
}
}
}
}
printf("%lld\n",ans);
return 0;
}
B网格(DP)
思路:
选择1走一步,花费为w1。选择2走两步,花费为w2。
先考虑只走选择1,则到(x,y)的花费为。
再考虑可以有选择2,我们要用魔法个点来优化之前的选择,则可以将魔法节点排序,那么就可以保证后面的魔法节点无法走到前面,这就无后效性了。再找子问题:
定义为到达第个魔法节点的距离,则有
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2005;
ll f[maxn];
struct Node {
int x,y;
}a[maxn];
int cmp(Node a,Node b) {
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
int main() {
int n,k,w1,w2;scanf("%d%d%d%d",&n,&k,&w1,&w2);
for(int i = 1;i <= k;i++) {
scanf("%d%d",&a[i].x,&a[i].y);
}
sort(a + 1,a + 1 + k,cmp);
a[k + 1].x = n;a[k + 1].y = n;
k++;
for(int i = 1;i <= k;i++) {
f[i] = 1ll * w1 * (a[i].x + a[i].y);
}
for(int i = 2;i <= k;i++) {
for(int j = 1;j < i;j++) {
if(a[j].x < a[i].x && a[j].y < a[i].y) {
int num = a[i].x + a[i].y - a[j].x - a[j].y - 2;
f[i] = min(f[i],f[j] + 1ll * num * w1 + w2);
}
}
}
printf("%lld\n",f[k]);
return 0;
}
C 有向无环图(二进制拆解)
思路:
一开始只想到了
1->2
1->3
3->4
2->4
这种的建图模式。
但实际上你直接先建成一条链(假设是n个点),然后第i个点向后面所有点连边。这时候就有神奇的事情:第i个点到点n的方案数为,
则再加一个源点0,0向第个点连边,方案数就会增加个, 这不就是二进制拆解吗?
而且刚好66个点,64个点表征二进制,两个点为原点,而且边数也就n^2级别,不会特别多。直接搞就好了
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
vector<pair<int,int> >vec;
int main() {
ll n,k;scanf("%llu%llu",&k,&n);
ll tmp = k;
int cnt = 0;
while(tmp) {
cnt++;
tmp /= 2;
}
if(n == 2 && k == 1) {
printf("2 1\n");
printf("1 2\n");
return 0;
} else if(n == 4 && k == 3) {
printf("4 5\n");
printf("1 2\n2 3\n3 4\n1 3\n2 4\n");
return 0;
}
int N = cnt + 2;
for(int i = 2;i <= cnt + 1;i++) {
for(int j = i + 1;j <= cnt + 2;j++) {
vec.push_back({i,j});
}
}
for(int i = 0;i < cnt;i++) {
if((k >> i) & 1) {
int nex = cnt - i + 1;
vec.push_back({1,nex});
}
}
printf("%d %d\n",N,(int)vec.size());
for(int i = 0;i < vec.size();i++) {
printf("%d %d\n",vec[i].first,vec[i].second);
}
return 0;
}
D 分数
思路:
打个表可以发现(事后也可以证明),对于第个分数的贡献,就是中质因子比多的部分。
而
当n为单个质数幂次时
否则
所以只需要求出所有位单个质数幂次的数就行了。
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 8e7 + 7;
const ll mod = 1ll << 32;
int a[5000000],cnt;
int v[maxn];
void getprime() {
for(int i = 2;i < maxn;i++) {
if(v[i] == 0) {
v[i] = i;a[++cnt] = i;
}
for(int j = 1;j <= cnt && i * a[j] < maxn;j++) {
v[i * a[j]] = 1;
if(i % a[j] == 0)break;
}
}
}
ll qpow(ll x,ll n) {
ll res = 1;
while(n) {
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
ll gcd(ll n,ll m) {
return m == 0 ? n : gcd(m,n % m);
}
int main() {
getprime();
// printf("debug %d\n",cnt);
ll n,A,B;scanf("%lld%lld%lld",&n,&A,&B);
for(int i = 2;i <= n;i++) {
v[i] = 0;
}
for(int i = 1;i <= cnt;i++) {
ll now = a[i];
while(now <= n) {
v[now] = i;
now = now * a[i];
}
}
for(int i = 2;i <= n;i++) {
if(v[i]) {
A = (A * a[v[i]] % mod + B) % mod;
}
}
printf("%lld\n",A);
return 0;
}
E 树数数
思路:
被拉去吃兰州拉面,写个暴力就跑了,有时间补补吧。
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 7;
int a[maxn],color[maxn];
int fa[maxn],vis[maxn];
vector<int>G[maxn];
void dfs1(int x) { //染色
vis[x] = 1;
if(x == 1) return;
dfs1(fa[x]);
}
int dfs2(int x) { //寻找
if(vis[x] && color[x] == 1) {
return a[x];
}
if(x == 1) return 0;
return dfs2(fa[x]);
}
vector<int>point;
void dfs3(int x,int fa) { //找u子树
point.push_back(x);
for(int i = 0;i < G[x].size();i++) {
int v = G[x][i];
if(v == fa) continue;
dfs3(v,x);
}
}
ll LCBA(int u) {
point.clear();
dfs3(u,fa[u]);
int len = point.size();
ll ans = 0;
for(int i = 0;i < len;i++) {
for(int j = 0;j < len;j++) {
if(i == j) continue;
memset(vis,0,sizeof(vis));
dfs1(point[i]);
ans += dfs2(point[j]);
}
}
return ans / 2;
}
int main() {
int n,m;scanf("%d%d",&n,&m);
for(int i = 2;i <= n;i++) {
int x;scanf("%d",&x);
fa[i] = x;
G[i].push_back(x);G[x].push_back(i);
}
for(int i = 1;i <= n;i++) {
scanf("%d",&a[i]);
}
for(int i = 1;i <= m;i++) {
char op[10];scanf("%s",op);
if(op[0] == 'Q') {
int u;scanf("%d",&u);
printf("%lld\n",LCBA(u));
} else if(op[0] == 'F') {
int x;scanf("%d",&x);
color[x] ^= 1;
} else if(op[0] == 'M') {
int x,y;scanf("%d%d",&x,&y);
a[x] = y;
}
}
return 0;
}
本文地址:https://blog.csdn.net/tomjobs/article/details/107898022