1006 Rikka with Graph

Rikka with Graph

  

   1
4 5
  

  

   14
  

当 $m\le n-1$ 时，我们需要最小化距离为 nnn 的点对数，所以肯定是连出一个大小为 m+1m+1 的联通块，剩下的点都是孤立点。在这个联通块中，为了最小化内部的距离和，肯定是连成一个菊花的形状，即一个点和剩下所有点直接相邻。

当 m>n−1m > n-1 时，肯定先用最开始 $n-1$ 条边连成一个菊花，这时任意两点之间距离的最大值是 22。因此剩下的每一条边唯一的作用就是将一对点的距离缩减为 11。

这样我们就能知道了最终图的形状了，稍加计算就能得到答案。要注意 mm 有可能大于 n(n−1)​​/2。

WA在了int*int的结果也会是int需要强转成longlong。。。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    while(~scanf("%d",&t)){
        while(t--){
            long long n;
            long long m;
            scanf("%lld%lld",&n,&m);
            long long res=0;
            if(m<n){
                long long temp=(n-m-1)*n;
                res=(temp+m)+(2*m-1+temp)*m+temp*(n-1);            
            }
            else{
                res = n-1+(1+2*(n-2))*(n-1)-2*(m-n+1);
                if(res<n*(n-1)){
                    res=n*(n-1);
                }
            }
            printf("%lld\n",res);    
        }
    }
    return 0;
}

1008 Rikka with Subset

Rikka with Subset

  

   2
2 3
1 1 1 1
3 3
1 3 3 1
  

  

   1 2
1 1 1

   

    

     Hint
    
 In the first sample, $A$ is $[1,2]$. $A$ has four subsets $[],[1],[2],[1,2]$ and the sums of each subset are $0,1,2,3$. So $B=[1,1,1,1]$
   
  

题意：

有两个数组a[ ]和b[ ]，给出两个数n和m，表示a[ ]中有 n 个数，所有数之和为 m ，然后又给出了b[ ]数组，b[ x ]数组中装的是a[ ]中和为 x 的子集个数。例如：a[ ]数组为[ 1，2 ]；那么它的子集有[ ]，[ 1 ]，[ 2 ]，[ 1，2 ]；这些子集的和分别为 0，1，2，3；所以b[ 0 ]=1，b[ 1 ]=1，b[ 2 ]=1，b[ 3 ]=1；现在给你b[]数组，让你求a[ ]数组。

网上的思路：

对于数组b，除了b[0]外，第一个值不为零的b[i]，在a数组里一定存在，且存在的个数就为b[i]个，因为a的子串包括那些只含有a数组某一个元素的，这些子串的和只有那一个元素的值，往往较小排在前面，这时候至少可以确定一个a中的元素，现在要做的是把这已经个确定的元素拿出来，并且对b进行操作，处理成除去 拿出去的那个元素 后，b数组继续满足原先的定义，就像刚开始那个元素就没有出现过一样。这个时候我们就可以重复上述的步骤，直到取出a数组中的全部元素。
下面的问题就是怎么对b数组进行处理：和为j的（总）组合数=和为j的组合数（含有i元素）+和为j的组合数（不含有i元素）我们的目的就是把各项处理成 和为j的组合数（不含有i元素） 的那种。和为j的（总）组合数为处理前的状态，已知。下面就是确定和为j的组合数（含有i元素）了，而 和为j的组合数（含有i元素）为 b[j-i] 个，因为有几种值为j的情况 可以由（j-i）+i得到，那么就有多种 和为j的组合数（含有i元素） ，所以为b[j-i]个。有 b[j]=b[j]-b[j-i];这一个等式 就可以了。

官方思路：

签到题，大致的思想就是反过来的背包。

如果 B​i​​ 是 BBB 数组中除了 B​0​​ 以外第一个值不为 0 的位置，那么显然 i 就是 AA中的最小数。现在需要求出删掉 i 后的 B 数组，过程大概是反向的背包，即从小到大让 B​j​​−=B​j−i​​。时间复杂度 O(nm)

#include<bits/stdc++.h>
using namespace std;
int b[10050];
int a[600];
int main()
{
    int T, n, m, k;
    scanf("%d", &T);
    while(T--)
    {
        k = 0;
        scanf("%d%d", &n, &m);
        for(int i = 0; i <= m; i++)
            scanf("%d", &b[i]);
        for(int i = 1; i <= m; )
        {
            if(k >= n)
                break;
            if(i <= 0)
                continue;
            if(b[i] != 0)
            {
                a[k++] = i;
                for(int j = i; j <= m; j++)
                    b[j] = b[j] - b[j - i];
            }
            else
                i++;
        }
        printf("%d", a[0]);
        for(int i = 1; i < k; i++)
            printf(" %d", a[i]);
        printf("\n");
    }

}

1011 Rikka with Competition

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 100005;
ll a[maxn];
bool cmp(ll a,ll b){
    return b<a;
}
int main(){
    std::ios::sync_with_stdio(false);
    ll t,n,k,temp;
    int ans;
    cin>>t;
    while(t--){
        ans = 0;
        cin>>n>>k;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        sort(a,a+n,cmp);
//        for(int i=0;i<n;i++){
//            cout<<a[i]<<" ";
//        }
//        cout<<endl;
        ans = 1;
        temp = a[0];
        for(int i=1;i<n;i++){
            if(temp-a[i]<=k){
                ans++;
                temp = a[i];
            }else{
                break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}