Anastasia and pebbles

题意：你有两种框，每个框可以最多装k重量的物品，但是你每个框不能装不一样的物品。现在地面上有n个物品，问你最少多少次，可以把这n个物品全部装回去。

题解：其实就是问你得用多少次框，然后把多少次除以2就好了。每次装k的物品装回去就好了。

代码：

#include
    
     using namespace std;const int maxn = 1e5+7;int a[maxn],n,k;int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++)        cin>>a[i];    sort(a+1,a+1+n);    long long ans = 0;    for(int i=1;i<=n;i++){        ans+=(a[i]+k-1)/k;    }    cout<<(ans+1)/2LL<
    

Masha and geometric depression

题意：给你一个b1,q，再给你一个l，m，和m个数a[i]。然后你需要把不等于a[i]，且小于等于l的数记录下来。

题解：直接暴力就好了，因为等比数列跑得特别快，如果要超过l的话，会很快的超过l了，而且如果答案有限的话，显然不会超过200？所以直接暴力吧。

代码：

#include
    
     using namespace std;set
     
       S;long long b,q,l,m;map
      
       H;int main(){    cin>>b>>q>>l>>m;    for(int i=0;i
       
        >k;        S.insert(k);    }    int time = 0;    int ans = 0;    long long now = b;    while(time<500000){        time++;        if(abs(now)>l)break;        if(S.find(now)==S.end()){            ans++;        }        now=now*q;    }    if(ans>30000){        cout<<"inf"<
       
      
     
    

Functions again

题意：定义f(l,r)=sigma(abs(a[i]-a[i+1)*(-1)^(i-l))，给你n个数，找到最大的f(l,r)

题解：跑一个前缀和，然后你要奇数位置开头的，那么就正常做。如果是偶数位置开始的话，那么就乘上一个-1就好了嘛。掏个set算前缀的最小值和最大值。

代码：

#include
    
     using namespace std;const int maxn = 1e5+7;long long a[maxn],b[maxn],c[maxn];int n;set
     
      A,B;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        cin>>a[i];    if(n==2){        cout<
      
       <
      
     
    

D. Weird journey

题意： 给你一个图，这个图有自环，现在问你有多少个路径满足可以经过m-2条边两次，剩下两条边一次。

题解：答案为 自环与自环相组合，自环和其他边组合，其他边和其他边组合。其中其他边和其他边组合的时候，必须要挨在一起。

代码：

#include
    
     using namespace std;const int maxn = 1e6+7;int n,m;vector
     
      E[maxn];int Cnt,flag[maxn],vis[maxn],d[maxn];void dfs(int x){    vis[x]=1;    for(int i=0;i
     
    

E. The Great Mixing

题意：现在有k个物品xi/1000，你现在可以任意挑选，并随便使用，你需要调制出n/1000的物品，问你最少使用多少个。

题解：首先去重，那么k最多只有1001了。然后我们让所有的xi减去n，然后就可以理解为凑0了，然后就可以跑完全背包。第一维的个数最多1000个，第二维的范围就是[-1000,1000]。

代码：

#include
    
     using namespace std;int n,k;const int maxn = 1e6+7;int a[maxn];vector
     
      v;map
      
        dp[2003];int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=k;i++){        scanf("%d",&a[i]);        a[i]-=n;        v.push_back(a[i]);    }    sort(v.begin(),v.end());    v.erase(unique(v.begin(),v.end()),v.end());    dp[0][0]=1;    map
       
        ::iterator it;    for(int i=1;i<=1002;i++){        for(it=dp[i-1].begin();it!=dp[i-1].end();it++){            for(int j=0;j
        
         first+v[j])>1000)continue;                dp[i][it->first+v[j]]=1;            }        }        if(dp[i].count(0)){            printf("%d\n",i);            return 0;        }    }    printf("-1\n");    //ax+by+...+t=n*1000(a+b+c+..+);}