title

比赛网址

训练结果

时间:‘’2020-08-01 12:00~17:00’’
rank:‘’196/1090’’
完成情况：‘’3/3/10’’

题解

B.Mask Allocation

题意

有 $n \times m$ 个物品，让你给一个划分方案，使得既能分成 $n$ 组 $m$ 个又能分成 $m$ 组 $n$ 个

题解

发现最优划分类似于 gcd 的做法，若 $n<m$ , 我们就用 $n$ 去补 $m$ ，补不了的部分就转化为了 $m \% n,n$ 的问题，递归处理。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int read()
{
    int k=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
int T,n,m,tot,ans[100055];
void solve(int x,int y)
{
    if(x>y) swap(x,y);
    if(!x) return;
    int res=y/x*x;
    for(int i=1;i<=res;i++)
        ans[++tot]=x;
    solve(y%x,x);
}
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    for(T=read();T;T--)
    {
        n=read();m=read();
        tot=0;solve(n,m);
        sort(ans+1,ans+1+tot,cmp);
        printf("%d\n",tot);
        for(int i=1;i<=tot;i++)
            printf("%d ",ans[i]);
        puts("");
    }
    return 0;
}

D.Fake News

题意

问平方和是否为完全平方数

题解

开始用python写高精度结果T了（人家用cin都T了更何况py），打了个表发现就只有1和24满足

H.Dividing

题意

一下数对是合法的

1、$(1,k)$是合法的

2、如果$(n,k)$合法，那么$(n+k,k)$合法

3、如果$(n,k)$合法，那么$(nk,k)$合法

给定范围$n,k \leq 10^{12}$，求范围内所有合法的数对

题解

容易发现$k$是不变的，那么只需对每个$k$求出$n$的个数

容易发现所有$(1+tk,k)$都是合法的

除此之外所有合法的必然是$k$的倍数，而且$k$的倍数一定能被凑出来

因此合法的只有$(tk,k)$和$(1+tk,k)$其中$t$为非负整数

只需要整除分块即可

记得特判$n,k$分别为$1$的情况= =

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f,P = 1000000007;
inline LL read(){
    LL out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
    while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
    return flag ? out : -out;
}
LL N,K,ans = 0;
int main(){
    cin >> N >> K;
    if (K == 1){cout << N % P << endl; return 0;}
    if (N == 1){cout << K % P << endl; return 0;}
    ans = (N + N + K - 2) % P;
    for (LL i = 3,nxt; i <= K && i <= N; i = nxt + 1){
        nxt = N / (N / i);
        if (nxt > K) nxt = K;
        ans = (ans + 1ll * (N / i) % P * ((nxt - i + 1) % P) % P) % P;
    }
    N--;
    for (LL i = 3,nxt; i <= K && i <= N; i = nxt + 1){
        nxt = N / (N / i);
        if (nxt > K) nxt = K;
        ans = (ans + 1ll * (N / i) % P * ((nxt - i + 1) % P) % P) % P;
    }
    N++;
    ans = (ans % P + P) % P;
    cout << ans << endl;
    return 0;
}

训练实况

训练总结

wxg: 这场发挥很差，c一直执着于一个错误算法。

hxm:菜是原罪，$H$调了很久才调出来特判没判，$A$是模拟退火而却不能正确写对

fyh:J是真的读不懂题，第一英语差，第二额是本身对指针，对象之类的玩意不熟悉。以后帮队友调题的时候要注意几点：特殊情况（n=1等等是否取模！！）

CVBB ACM Team

目录

title

训练结果

题解

B.Mask Allocation

题意

题解

D.Fake News

题意

题解

H.Dividing

题意

题解

训练实况

训练总结

CVBB ACM Team

用户工具

站点工具

目录

title

训练结果

题解

B.Mask Allocation

题意

题解

D.Fake News

题意

题解

H.Dividing

题意

题解

训练实况

训练总结

页面工具