A.[思考题]神秘任务1

题意

神秘人给了两个数字，分别表示 n 和 k，并要求 TT 给出 k 个奇偶性相同的正整数，使得其和等于 n。

例如 n = 10，k = 3，答案可以为 [4 2 4]。

样例

样例输入：

第一行一个整数 T，表示数据组数，不超过 1000。
之后 T 行，每一行给出两个正整数，分别表示 n（1 ≤ n ≤ 1e9）、k（1 ≤ k ≤ 100）。

8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9

样例输出:

如果存在这样 k 个数字，则第一行输出 “YES”，第二行输出 k 个数字。
如果不存在，则输出 “NO”。

YES
4 2 4
YES
55 5 5 35
NO
NO
YES
1 1 1 1 1 1 1 1
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120

---

思路

1.刚看到题时,试图先计算n%k n/k 试图找找规律 举了几个例子之后 发现了一些规律:

令a=n%k b=n/k
我们先把n 分成k个 n/k
①当b为奇数时
(1)a为奇数时
若k为奇数 例:10÷3=3···1 先列出 3 3 3 还剩余一个1 我们只需令第一个3减一 第二个3加一 再把剩的1加到最后的3上即可
若k为偶数 例: 7÷2=3···1 先列出3 3 剩余一个1 此时无论怎么操作 都不可以
(2)a为偶数时
例: 8÷3=2···2 或14÷4=3···2 都可以吧这个余数a加到任意一个n/k上就好

②当b为偶数时
(1)a为奇数时
同①
(2)a为偶数时
同①

故我们只需要分别判断一下b a k的奇偶性就好啦
(对于b奇a奇k奇和b偶a奇k奇的情况 我们需要把前k/2个元素减一 往后k/2个元素+1 再让最后一个元素+a即可 同时由于必须为正整数 所以当出现0时也不可

---

总结

因为可以看出对于每一种情况 无论n k的数据是多大 他们的规律都是固定的 因此举了一些小数据的例子来找出规律

---

代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
using namespace std;
int T,n,k;
int ans[110];
bool isOdd(int x)
{
    
    if(x%2==1)  return true;
    else return false;
}
int main()
{
    
    cin>>T;
    while(T--)
    {
    
        cin>>n>>k;
        memset(ans,0,sizeof(ans));
        int a=n%k,b=n/k;
        for(int i=1;i<=k;i++)   ans[i]=b;
        if(isOdd(b)&&isOdd(a)&&!isOdd(k)||!isOdd(b)&&isOdd(a)&&!isOdd(k)||b==0)   
        {
    cout<<"NO"<<endl;continue;}   
        else if(!isOdd(b)&&!isOdd(a)||isOdd(b)&&!isOdd(a))
        {
    
            ans[k]+=a;
            cout<<"YES"<<endl;
            for(int i=1;i<=k;i++)   cout<<ans[i]<<" ";
            cout<<endl;
        }else
        {
    
            ans[k]+=a;
            int flag=1;
            for(int i=1;i<=k/2;i++) 
            {
    
                ans[i]--;
                if(ans[i]==0)   {
    cout<<"NO"<<endl;flag=0;break;}//必须为正整数 不能为0
            }
            if(flag==0) continue;
            for(int i=k/2+1;i<=k-1;i++) ans[i]++;
            cout<<"YES"<<endl;
            for(int i=1;i<=k;i++)   cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
    system("pause");
    return 0;
}

B.[思考题]神秘任务2

题意

任务依旧只给了两个数字，分别表示 n 和 k，不过这一次是要求 TT 给出无法被 n 整除的第 k 大的正整数。
例如 n = 3，k = 7，则前 7 个无法被 n 整除的正整数为 [1 2 4 5 7 8 10]，答案为 10。

样例

样例输入：

第一行一个整数 T，表示数据组数，不超过 1000。
之后 T 行，每一行给出两个正整数，分别表示 n（2 ≤ n ≤ 1e9）、k（1 ≤ k ≤ 1e9）。

6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1

样例输出：

对于每一组数据，输出无法被 n 整除的第 k 大的正整数。

10
15
1999999999
113
1000000001
1

---

思路

我们可以将所有数 看成每n-1个数为一组 然后判断k是在第几组中
a=k%(n-1),b=k/(n-1);
算出组数后 我们只需将组数*n 再加余数 即可得到第K大正整数
Tips:若余数是0 代表在上一组的最后 故我们要将ans-1

---

总结

这个题与T1相较好思考一点

---

代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
using namespace std;
int T;
long long n,k,ans;
bool isOdd(int x)
{
    
    if(x%2==1)  return true;
    else return false;
}
int main()
{
    
    //计算出能被n整除的数
    cin>>T;
    while(T--)
    {
    
        cin>>n>>k;
        long long a=k%(n-1),b=k/(n-1);
        ans=b*n;
        if(a==0)    ans-=1;
        else ans+=a;
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}
}

C.[DP]接猫

题意

捡猫咪游戏是这样的，猫咪从天上往下掉，且只会掉在 [0, 10] 范围内，具体的坐标范围如下图所示。

TT 初始站在位置五上，且每秒只能在移动不超过一米的范围内接住掉落的猫咪，如果没有接住，猫咪就会跑掉。例如，在刚开始的一秒内，TT 只能接到四、五、六这三个位置其中一个位置的猫咪。

喜爱猫咪的 TT 想要接住尽可能多的猫咪，你能帮帮他吗？

样例

样例输入：

多组样例。每组样例输入一个 m (0 < m < 100000)，表示有 m 只猫咪。
在接下来的 m 行中，每行有两个整数 a b (0 < b < 100000)，表示在第 b 秒的时候有一只猫咪掉落在 a 点上。
注意，同一个点上同一秒可能掉落多只猫咪。m = 0 时输入结束。

6
5 1
4 1
6 1
7 2
7 2
8 3
0

样例输出:

输出一个整数 x，表示 TT 可能接住的最多的猫咪数。

4

---

思路

1.读完题后 直觉上认为是一道DP 可以用dp[t][x]记录第t秒 在x位置上可以接到猫猫的最大值
10^5*11的复杂度很可以接受 于是考虑dp的转移方程

2.转移方程:
dp[i][j]可以从 dp[i-1][j] dp[i-1][j-1] dp[i-1][j+1]三个位置转移过来(每秒只能移动一格)
故 dp[i][j]=max(dp[i-1][j] dp[i-1][j-1] dp[i-1][j+1])+cat[i][j]
答案: max(dp[maxt][i])

3.限制
由于初始时TT在位置5上 故第一秒时 TT只能在4 5 6三个位置
第二秒时 TT只能在 3 4 5 6 7 五个位置
···依次类推
故用数组v[]来限制

---

总结

很明显的一道DP题 只需要找到dp的状态和转移方程就好啦~

---

代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#define MAXN 100010
using namespace std;
int m;
int cat[MAXN][11];//cat[t][i] 表示 在第t秒 i位置上的猫的数量
int dp[MAXN][11];
int can[MAXN][11];
void initialize()
{
    
    can[1][0]=can[1][1]=can[1][2]=can[1][3]=can[1][7]=can[1][8]=can[1][9]=can[1][10]=0;
    can[2][0]=can[2][1]=can[2][2]=can[2][8]=can[2][9]=can[2][10]=0;
    can[3][0]=can[3][1]=can[3][9]=can[3][10]=0;
    can[4][0]=can[4][10]=0;
}
int main()
{
    //dp?  dp[i][j] 表示 第i秒 在j位置上时能接到猫的最大数量
    while(true)
    {
    
        cin>>m;
        if(m==0)    break;
        memset(cat,0,sizeof(cat));
        memset(dp,0,sizeof(dp));
        memset(can,1,sizeof(can));
        
        initialize();
        int t,x,maxt=0;
        for(int i=1;i<=m;i++)   
        {
    
            cin>>x>>t; 
            maxt=max(maxt,t);
            cat[t][x]++;
        }

        for(int i=1;i<=maxt;i++)
            for(int j=0;j<=10;j++)
            {
    
                if(!can[i][j])  continue;
                if(j==0)    dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+cat[i][j];
                else if(j==10)  dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+cat[i][j];
                else    dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-1],dp[i-1][j+1]))+cat[i][j];
                
            }
        int ans=0;
        for(int i=0;i<=10;i++)  ans=max(ans,dp[maxt][i]);
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}

D.[树型DP]苹果树

题意

已知树上共有 N 个节点，每个节点对应一个快乐值为 w[i] 的苹果，为了可持续发展，TT 要求摘了某个苹果后，不能摘它父节点处的苹果。
TT 想要令快乐值总和尽可能地大，你们能帮帮他吗？

样例

样例输入：

结点按 1～N 编号。
第一行为 N (1 ≤ N ≤ 6000) ，代表结点个数。
接下来 N 行分别代表每个结点上苹果的快乐值 w[i]（-128 ≤ w[i] ≤ 127)。
接下来 N-1 行，每行两个数 L K，代表 K 是 L 的一个父节点。
输入有多组，以 0 0 结束。

7
1
1
1
1
1
1
1
1 3
7 4
2 3
4 5
6 4
3 5
0 0

样例输出：

每组数据输出一个整数，代表所选苹果快乐值总和的最大值。

5

---

思路

1.很经典的一道树型DP题 因为树结构非常明显

2.考虑一下状态 dp[i][0/1]分别表示 第i个点去或不去时 以i为根的子树能获得的最大快乐值

3.状态转移:
dp[i][1]时 他的所有直接孩子都不能去 故dp[i][1]=segma(dp[v][0])+w[i]
dp[i][0]时 他的孩子可以去 也可以不去 故dp[i][0]=segma(max(dp[v][0],dp[v][1]))

4.答案
max(dp[root][0],dp[root][1])

5.只需要从根开始 向下dfs即可

---

总结

树型DP特殊的一点在于是在树上的DP(好像确实是废话TAT)

所以特殊的地方在于 是递归的DP思路 而不是一般的DP时的递推思路

---

代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<vector>
#define MAXN 6010
using namespace std;
int n;
int w[MAXN];
int dp[MAXN][2],fa[MAXN];
vector<int> G[MAXN];
void dfs(int x)
{
    
    for(int j=0;j<G[x].size();j++)
    {
    
        int v=G[x][j];
        dfs(v);
        dp[x][0]+=max(dp[v][1],dp[v][0]);
        dp[x][1]+=dp[v][0];
    }
    dp[x][1]+=w[x];
}
int main()
{
    
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>w[i];
    int l,k;
    for(int i=1;i<=n-1;i++)//k是l的一个父节点 初始化树
    {
    
        cin>>l>>k;
        G[k].push_back(l);
        fa[l]=k;
    }

    for(int i=1;i<=n;i++)
    {
    
        if(fa[i]==0)//没有上司
        {
    
            dfs(i);
            cout<<max(dp[i][0],dp[i][1])<<endl;
        }
    }
    system("pause");
    return 0;
}

E.[单调队列优化DP]神秘任务3

题意

给定一个环，A[1], A[2], A[3], … , A[n]，其中 A[1] 的左边是 A[n]。要求从环上找出一段长度不超过 K 的连续序列，使其和最大。

样例

样例输入：

第一行一个整数 T，表示数据组数，不超过 100。
每组数据第一行给定两个整数 N K。（1 ≤ N ≤ 100000, 1 ≤ K ≤ N）
接下来一行，给出 N 个整数。（-1000 ≤ A[i] ≤ 1000）。

4
6 3
6 -1 2 -6 5 -5
6 4
6 -1 2 -6 5 -5
6 3
-1 2 -6 5 -5 6
6 6
-1 -1 -1 -1 -1 -1

样例输出:

对于每一组数据，输出满足条件的最大连续和以及起始位置和终止位置。
如果有多个结果，输出起始位置最小的，如果还是有多组结果，输出长度最短的。

7 1 3
7 1 3
7 6 2
-1 1 1

---

思路

1.首先思考如何处理环？
将序列长度扩展到2*n-1 即将环剪开 例:1 2 3 4 (1) 可以拆成链 1 2 3 4 1 2 3

2.拆成链后 如何在链上计算有限制的最大连续序列和呢？
先维护前缀和

可以采用贪心的思想 即枚举每个点作为序列的右端点i
然后从[i-k,i]中找到一个j 使得sum[j]最小 这样sum[i]-sum[j-1]就是最大的了

考虑到这里后 我们发现需要维护部分区间上的最小值 于是可以考虑用单调队列来维护这个最小值
就可以把O(nk)的复杂度优化到O(n)

---

总结

由于要用到部分区间上的最小值 故考虑用单调队列来维护

TIPS:本题中 由于sum[i]-sum[j]指的是[j+1,i]这个区间 而右端点实际上是从[i-k,i]的 当j=i时 会出现[i+1,i]的诡异情况 所以我们在维护单调队列时 先进行维护区间大小 然后更新max值 最后再用sum[i]维护单调性 为i+1的计算做准备即可

---

代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<deque>
#define MAXN 200010
using namespace std;
int T,n,k;
long long a[MAXN],sum[MAXN];
struct section
{
    
    int l;
    int r;
};
int main()
{
    
    cin>>T;
    while(T--)
    {
    
        cin>>n>>k;
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)   scanf("%lld",&a[i]),a[i+n]=a[i];//拆环成链+前缀和
        for(int i=1;i<=2*n-1;i++)   sum[i]=sum[i-1]+a[i];//前缀和
        long long ans=-0x7ffff;
        section cur;
        cur.l=0;cur.r=0;
        deque<int> q;
        q.push_back(0);
        for(int i=1;i<=2*n-1;i++)//以i为右端点 从[i-m,i]中找到一个最小的sum 用sum[i]-min即为以i为右端点的最大字段和
        {
    
            while(!q.empty()&&q.front()<i-k)//维护窗口大小
                q.pop_front();

            long long tmp=sum[i]-sum[q.front()];//先计算 后用sum[i]维护单调队列 为下一次循环做准备
            if(tmp>ans)
            {
    
                ans=tmp;
                cur.l=q.front()+1;
                cur.r=i;
            }    
            while(!q.empty()&&sum[q.back()]>sum[i])//维护一个从头到尾递增的序列 即q.front()是min
                q.pop_back();
            q.push_back(i);
            
            
        }
        if(cur.l>n) cur.l-=n;
        if(cur.r>n) cur.r-=n;
        cout<<ans<<" "<<cur.l<<" "<<cur.r<<endl; 
    }
    system("pause");
    return 0;
}