hdu6

1004:

有 𝑛n 只猫排成一个序列，从左到右第 𝑖i 只猫的编号为 𝑝𝑖pi​，其中 𝑝p 是一个 11 到 𝑛n 的排列。在一次操作中， cats 可以选择：

• 将一个新的传送门插入到序列中。可以插入到序列中最左侧的物品（猫或传送门）的左侧，最右侧的物品的右侧，或任意两个物品之间。
• 选择一只猫和一个在序列中的传送门，将猫从其原本位置移除。然后，将猫插入到到传送门的左侧。如果传送门左侧有其他物品，则将猫插入到传送门与其左侧物品之间。
• 选择一只猫和一个在序列中的传送门，将猫从其原本位置移除。然后，将猫插入到到传送门的右侧。如果传送门右侧有其他物品，则将猫插入到传送门与其右侧物品之间。

在所有操作完成后，cats 会移除序列中所有的传送门，不改变序列中猫的相对位置。

cats 希望通过操作将猫按编号从小到大排序，即在所有操作结束后，从左到右第 𝑖i 只猫的编号为 𝑖i。在此基础上，cats 希望最小化操作的总次数。你能告诉 cats 最少需要多少次操作才能将猫排序吗？

Input

第一行包含一个整数 𝑇T （1≤𝑇≤2⋅1041≤T≤2⋅104），表示一共有 𝑇T 组测试数据。

对于每组测试数据：

第一行为一个整数 𝑛n （1≤𝑛≤2⋅1051≤n≤2⋅105），表示猫的总数。

第二行为 𝑛n 个整数 𝑝1,𝑝2,…,𝑝𝑛p1​,p2​,…,pn​ （1≤𝑝𝑖≤𝑛1≤pi​≤n），表示初始时猫的编号。保证 𝑝p 是一个 11 到 𝑛n 的排列。

保证所有测试数据的 𝑛n 之和不超过 106106。

Output

对于每组测试数据，输出一个整数，表示 cats 最少需要的操作次数。

Sample Input

5 1 1 3 2 3 1 7 1 3 2 4 6 5 7 6 6 5 4 3 2 1 15 14 12 6 7 1 3 5 8 11 13 15 9 10 4 2

Sample Output

0 2 4 6 12

官方题解：

考虑所有没有被传送的数，它们一定构成原来的序列中的一个单调递增
的子序列，所有不在子序列中的数则需要被操作。每一段（数值上）连续
的，需要被操作的数可以使用同一个传送门传送。总操作次数即为所有
被操作的数的总数与所有被操作的数组成的连续段数之和。
•设dpj表示以pj为结尾的子序列需要操作次数的最小值，考虑子序列中
前一个数pi，如果pi+1=pj，则不需要插入连续段，更新为
dpj=min(dpj,dpi)。如果pi+1<pj，则需要插入一个含有pj−pi−1个
数的连续段。则有dpj=min(dpj,dpi+pj−pi)。
•对于数组两侧的需要被操作的数的连续段，可以通过在排列p开头放入
一个0，末尾放入一个n+1解决。第一种转移可以直接O(n)做，第二
种转移可以用树状数组快速维护pj所有满足i<j，pi+1<pj的位置
dpi−pi的min实现。
•总时间复杂度为O(nlogn)。

个人思路解释：

dpj表示以pj为结尾的子序列需要操作次数的最小值，考虑子序列中
前一个数pi

如果pi+1=pj，则不需要插入连续段==》dpj=min(dpj,dpi)

pi+1<pj===》我们可以理解为在i前面找到一个数j,j<i,dpj表示以j结尾的串已经连续,现在我们还需要安置1个传送门&进行i-j-1次传送，总次数i-j；==》所以dpj=min(dpj,dpi+pj−pi)。

很显然，dpj-j由j决定

这里的j是比i小同时位置在i前面的所有数，我们需要维护这个最小值

这种前缀最小值的维护一般会想到树状数组

==》code:

#include<bits/stdc++.h>
using namespace std;
int p[200002],pos[200002],dp[200002],tre[200010],N,inf=1000000000;
int lowbit(int x){
    return x-(x&(x-1));
}
void add(int p,int vl){
    for(;p<=N;p+=lowbit(p))tre[p]=min(tre[p],vl);
}
int qry(int p){
    int vl=inf;
    for(;p>0;p-=lowbit(p))vl=min(vl,tre[p]);
    return vl;
}
void clr(){
    int i;
    for(i=0;i<=N;i++)tre[i]=inf;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T,n,i,c,ans;
    for(cin>>T;T>0;T--)
    {
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>p[i];
            pos[p[i]]=i;
        }
        p[0]=0;
        pos[0]=0; 
        p[n+1]=n+1;
        pos[n+1]=n+1;
        n+=2;
        N=n;
        clr();
        for(i=0;i<n;i++)dp[i]=inf;
        dp[0]=0;
        for(i=0;i<n;i++)
        {
            if(i>0&&pos[i]>pos[i-1])dp[i]=min(dp[i],dp[i-1]);
            dp[i]=min(dp[i],qry(pos[i])+i);
            add(pos[i]+1,dp[i]-i);
        }
        cout<<dp[n-1]<<'\n';
    }
    return 0;
}

1008:

cats 给出了一个 𝑛×𝑚n×m 的矩阵 𝑎𝑖,𝑗ai,j​，现在 cats 要在这 𝑛n 行中选出 𝑘k 行，假设选出的行编号依次为 𝑝1,𝑝2,…,𝑝𝑘p1​,p2​,…,pk​（序列 𝑝p 中的元素各不相同，且在 [1,𝑛][1,n] 中），定义该方案的权值为：∑𝑖=1𝑚(max⁡{𝑎𝑝1,𝑖,𝑎𝑝2,𝑖,…,𝑎𝑝𝑘,𝑖})i=1∑m​(max{ap1​,i​,ap2​,i​,…,apk​,i​})现在 cats 想知道所有选择方案中权值的最大值。

Input

第一行一个整数 𝑡t（1≤𝑡≤10001≤t≤1000），表示总的数据个数。

接下来包含 𝑡t 组数据，每组数据第一行三个整数 𝑛,𝑚,𝑘n,m,k（1≤𝑘≤𝑛≤10001≤k≤n≤1000 ，1≤𝑚≤131≤m≤13），依次表示矩阵 𝑎𝑖,𝑗ai,j​ 的行数和列数以及可以选择的行数。

接下来的 𝑛n 行，每行包含 𝑚m 个整数，其中第 𝑖i 行第 𝑗j 列表示 𝑎𝑖,𝑗ai,j​（0≤𝑎𝑖,𝑗≤1090≤ai,j​≤109）。

数据保证对于所有数据的 𝑛n 的和不超过 2×1052×105，且 𝑚m 大于 55 的数据的组数不超过 1010 组。

Output

共 𝑡t 行，依次表示这 𝑡t 组数据的结果。

Sample Input

3 3 4 2 3 2 2 2 1 4 1 1 4 1 1 1 3 3 2 1 1 1 1 2 3 3 4 5 5 3 4 1 1 4 5 1 4 1 9 1 9 8 1 2 3 3

Sample Output

11 12 22

很显然，如果k>=m,我们直接取每一列的最大值就行，所以我们考虑k<m的情况

其实很容易想到状态压缩dp,对于每一种状态，我们尝试寻找它在不同行的最大值，记录这个最大值，最终的结果能够被拆分成不超过k个最大状态的组合

1.状态如何求值

对于一个状态i，i&(i-1)表示它末位的i,将这个i开log就是该行数的位置

状态i=状态i去掉末位的状态+末位值

val[j]=val[j&(j-1)]+a[lo2[j-(j&(j-1))]];

2.状态转移方程

定义dp[第几遍转移][当前状态]；

dp[转移次数+1][当前状态+添加状态]=max(自身，dp[转移次数][当前状态]+添加状态的最大值

添加状态是当前状态关于总状态的补集的每种情况的遍历

for(int t=(1<<m)-1-j;t>0;t=((t-1)&((1<<m)-j-1)))//遍历所有添加状态

dp[i+1][j+t]=max(dp[i+1][j+t],dp[i][j]+maxval[t]);//转移

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll val[1<<13],maxval[1<<13],dp[14][1<<13];
ll a[14];
ll lo2[1<<13];
void init(){
    for(int i=0;i<13;i++){
        lo2[1<<i]=i;
    }
}
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    k=min(k,m);
    memset(val,0,sizeof(val));
    memset(maxval,0,sizeof(maxval));
    //memset(0,dp,sizeof(0));
    for(int i=0;i<=k;i++){
        for(int j=0;j<(1<<m);j++){
            dp[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[j];
        }
        for(int j=1;j<(1<<m);j++){
            val[j]=val[j&(j-1)]+a[lo2[j-(j&(j-1))]];
            maxval[j]=max(maxval[j],val[j]);
        }
    }
    for(int i=0;i<k;i++){
        for(int j=0;j<(1<<m);j++){
            for(int t=(1<<m)-1-j;t>0;t=((t-1)&((1<<m)-j-1))){
                dp[i+1][j+t]=max(dp[i+1][j+t],dp[i][j]+maxval[t]);
            }
        }
    }
    cout<<dp[k][(1<<m)-1]<<"\n";
}
int main(){
     ios::sync_with_stdio(false),cin.tie(0);
     init();
     int o;
     cin>>o;
     while(o--){
         solve();
     }
    // cout<<lo2[8];
}

nk7

Problem J. 象牙 Input file: standard input Output file: standard output Time limit: 5 seconds Memory limit: 1024 megabytes 给定四个正整数 a, b, c, d。计算 gcd(a^b , c^d ) 的值，并将其对 998244353 取模。 Input 第一行包含一个整数 t (1 ≤ t ≤ 105 )，表示测试用例的数量。 对于每个测试用例，输入只有一行，包含四个正整数 a, b, c, d (1 ≤ a, b, c, d ≤ 1018)。 Output 对于每个测试用例，输出一行一个整数，表示 gcd(a b , cd ) 对 998244353 取模后的结果。 Example standard input standard output 5 2 3 3 2 4 2 8 1 6 2 9 1 7 1 11 1 10000000000000 1 10000000000000 1 1 8 9 1 586315999

数学题，我们能够计算的只有两个底数的gcd,所以尝试如下转化

不妨设

b ≤ d，e=gcd(a,c),e^m1 *x1=a,e^m2 *x2=c,

==>

gcd(a^b,c^d)=gcd(e^(m1*b)*x1^b,e^(m2*d)*x2^d)=e^(m1*b)*gcd(x1^b,e^(m2*d-m1*b)x2^d),

因为x1,x2互质，所以gcd(x1,x2)=1;

原式被转化为e^(m1*b)*gcd(x1^b,e^(m2*d-m1*b))

递推求解

code:

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using lll = __int128;
#define all(x) (x).begin(),(x).end()
const ll p = 998244353;
ll ksm(ll x, lll Y)
{
    ll r = 1;
    x %= p;
    if (!Y) return 1;
    if (!x) return 0;
    ll y = Y % (p - 1);
    while (y)
    {
        if (y & 1) r = r * x % p;
        x = x * x % p; y >>= 1;
    }
    return r;
}
ll f(ll a, lll b, ll c, lll d)
{
    ll x = gcd(a, c);
    if (x == 1 || b == 0 || d == 0) return 1;
    lll ka = 0, kc = 0;
    while (a % x == 0) a /= x, ++ka;
    while (c % x == 0) c /= x, ++kc;
    ka *= b, kc *= d;
    if (ka > kc) swap(a, c), swap(b, d), swap(ka, kc);
    return ksm(x, ka) * f(a, b, x, kc - ka) % p;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << f(a, b, c, d) << '\n';
    }
}