A,H,K,N

DMy teammates didn't want to write anymore.之后可能会把C（ntt）和L（计算几何）补了

A题
背包,贪心,数学
题意：给定n个物品,每个物品有一个w值和p值,I want you to choosemand to thismThe items are sorted so that the value of the following formula is the largest.

对于这个公式,We can obviously see thatmThe order of items has an impact on the answer to this formula.

We consider it,前,后,Insert in three directionsmlook at the original itemm-1value of an item.
发现中,The formula derivation is difficult after rear insertion,The derivation of the formula inserted in front is simple
The front insert item is (w,p)Then the new value isw+p原价值
Obviously, it can be ordered according to the insertion value,
对于aThe inserted value is greater thanbThe condition for inserting the value is just that：Wa+Pa(Wb+Pbpre)>Wb+Pb(Wa+Papre)
化简后有
Wa+PaWb>Wb+Pb*Wa

After sorting, just pack the backpack from the front to the back and greedily select the one with the largest insertion value.
However one-dimensional01Backpacks select items from back to front,So we let the collation be Wa+PaWb<Wb+PbWa

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct node
{
    
    double p,w;
};
const int N =1e5+100;
int n,m;
node a[N];
double dp[N];
bool cmp(const node &a,const node &b)
{
    
    return a.w+a.p*b.w<b.w+b.p*a.w;
}
int main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i].w;
    for(int i=1;i<=n;i++)
    {
    
        cin>>a[i].p;
        a[i].p/=10000.0;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=min(i,m);j>=1;j--)
            dp[j]=max(dp[j],a[i].w+a[i].p*dp[j-1]);
    cout<<fixed<<setprecision(12)<<dp[m]<<endl;
    return 0;
}

H
构造,数学
题意：给定一个整数n,then has a length of n砖1块,n-1的2块,一直到长度为1的砖n块,These bricks are all widths1
You are required to build a rectangular wall with all the bricks,Output the number of solutions with the smallest perimeter of this wall and the upper left and lower right corners of each brick.

思路：The first is perimeter,We know that the area is fixed,又知area=n*m.So you can enumerate the closest onesn和m值

Then let the length be the smallest case,Layer by layer of bricks is enough

#include <iostream>

using namespace std;
int l,h,num[200+100];
int main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        int n,area=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            area+=(n-i+1)*i;
            num[i]=n-i+1;
        }
        for(int i=1;i*i<=area;i++)
        {
    
            if(area%i==0)
            {
    
                l=area/i;
                h=i;
            }
        }
        cout<<(l+h)*2<<endl;
        for(int i=0;i<h;i++)
        {
    
            int temp=0;
            while(temp<l)
            {
    
                int j=min(n,l-temp);
                while(!num[j])
                {
    
                    j--;
                }
                cout<<temp<<" "<<i<<" "<<temp+j<<" "<<i+1<<endl;
                temp+=j;
                num[j]--;
            }
        }
    }
    return 0;
}

K
SB
题意：变量aTo traverse sequentially1到n,当且仅当a取模n同余于i（i代表1-n的第i个数）时算i被遍历了,and can continue to traverse the next item.a的初始值为0,Can be done before traversal0-x次操作.Find the minimum number of operations required to traverse the entire array
操作定义：a=a*10+x（x是从0到9的任意一个数）

思路：Prime Minister Yizhin为1In case the answer is yes0.
遍历第i项时,aThe value is modulo n肯定是i-1,That is, the effective part isi-1,也就是a就可以当做i-1考虑.

a进行一次操作,能和a取模于nCongruent numbers are more.
第一次操作
[a10%n,a10%n+10)(This maximum value cannot be obtained)
第二次操作
[a1010%n,a1010%n+10*10)
以此类推

所以只要让i%n或者i%n+nIt's fine in this range

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int calc(int x,int y)
{
    
    int cnt=1,len=10;
    x=10*x%n;
    while(1)
    {
    
        int l=x,r=x+len;
        if((y>=l&&y<r)||(y+n>=l&&y+n<r))
            return cnt;
        ++cnt;
        len*=10;
        x*=10;
        x%=n;
    }
}
int main()
{
    
    cin>>n;
    if(n==1)
    {
    
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n;++i)
    {
    
        ans+=calc(i-1,i%n);
    }
    cout<<ans<<endl;
    return 0;
}

N
思维题
题意：给定n个数,这nYou can choose any two numbers and do itand和orThe operation yields two values,The array becomes stable after infinite operations,Ask the variance of this stable array.

It's easy to think of bit operations on binary states,Align two numbers,Only when the binary digits of the two numbers are different will the corresponding binary digits be exchanged0和1.Same time no change.So the final stable array should be polarized from a binary perspective.

比如：010 110 001最终会变成111 010 000.
Then there is the process of finding variance.
Found according to the data range up to 1e25.爆longlong当时int128可以接受.
Another way is to optimize the formula.

#include <iostream>

using namespace std;
#define ll __int128
const ll N = 1e5+100;
ll a[N];
ll bit[20];
ll b[N];
__int128 read()
{
    
    __int128 f=1,w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
    
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
    
        w=w*10+ch-'0';
        ch=getchar();
    }
    return f*w;
}
void print(__int128 x)
{
    
    if(x<0)
    {
    
        putchar('-');
        x=-x;
    }
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
ll gcd(ll a,ll b){
    
return b==0?a:gcd(b,a%b);
}
int main()
{
    
    ll n;
    n=read();
    for(ll i=1;i<=n;i++)
    {
    
        a[i]=read();
        for(ll j=0;j<=15;j++)
        {
    
            ll temp=(a[i]>>j);
            if(temp&1)
            {
    
                bit[j]++;
            }
        }
    }
    for(ll i=1;i<=n;i++)
    {
    
        for(ll j=15;j>=0;j--)
        {
    
            if(bit[j])
            {
    
                bit[j]--;
                b[i]+=1<<j;
            }
        }
    }
    ll sum=0;
    ll sum1=0;
    for(ll i=1;i<=n;i++)
    {
    
        sum+=b[i];
    }
    for(ll i=1;i<=n;i++)
    {
    
        sum1+=(n*b[i]-sum)*(n*b[i]-sum);
    }
    ll mm=n*n*n;
    print(sum1/gcd(sum1,mm));
    printf("/");
    print(mm/gcd(sum1,mm));
    return 0;
}

Do two moreSAThe question is off work today.