标签归档:枚举

Comet OJ 六一欢乐赛

题目链接:宝可梦中心大对决

已知共有 n 只皮卡丘,给出每只皮卡丘后背的数字,请你选择尽量多的皮卡丘上场,使得它们后背的数满足任意两个数字互质。只需输出你最多能选择了多少只皮卡丘。

估算一下复杂度,二进制枚举+直接判断就可过.当然也可以使用递归+预处理两个数是否互质,这样更快.

code:
暴力法:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}

int a[20];
int t[20];
int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i < pow(2, n); ++i) {
      int j = i;
      int p = 0, k = 0;
      while (j) {
        if (j & 1) t[p++] = a[k];
        k++;
        j >>= 1;
      }
      int flag=1;
      for (int q = 0; q < p; ++q) {
        for (int m = q+1; m < p; ++m) {
          if (gcd(t[q], t[m]) != 1) {
             flag=0;
             break;
          }
        }
        if(!flag) break;
      }
      if(flag) ans=max(ans,p);
    }
    cout << ans << endl;
  }

  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}

预处理+位元压缩:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}

int coprime[20];
int n;
int ans;
int a[20];
void pre(){
  for(int i=0;i<n;++i){
    coprime[i]=0;
    for(int j=0;j<n;++j){
      if(i!=j&&gcd(a[i],a[j])==1){
        coprime[i]|=1<<j;
      }
    }
  }
}

void dfs(int id,int cnt,int choosen_mark){
  if(id==n){
    if(ans<cnt)  ans=cnt;
    return;
  }
  if((coprime[id]&choosen_mark)==choosen_mark)
    dfs(id+1,cnt+1,choosen_mark|(1<<id));
  dfs(id+1,cnt,choosen_mark);
}

int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T;
  cin >> T;
  while (T--) {
    cin>>n;
    for(int i=0;i<n;++i){
      cin>>a[i];
    }
    ans=0;
    pre();
    dfs(0,0,0);
    cout << ans << endl;
  }
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}

前者要300多ms,后者只要2ms.

洛谷P1023 税收与补贴问题

考完数电,又要开始入坑了...(●'◡'●)

链接:洛谷P1023

这题理解题意很重要啊,我看了半天它的样例,感叹这样例都不是线性的啊,后来发现是我理解题意错了,相邻价位的销量变化是线性的,这里指的是给出的相邻价位之间的销量变化是线性的,然后中间空缺的价位销量就要依靠此求出.

要求绝对值最小,一开始我直接min(fabs(resMin),fabs(resMax)),这是不对的,在可行解区间左右端点一正一负的情况下,显然绝对值最小的点是0啊. 说明可行解区间的概念在写的时候还没想清楚.还是不够熟练.

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define maxn 200005
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int price[100005];
int num[100005];

int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int a,n;
  cin>>a;
  int x,y;
  int m=1;
  int maxprice=0;
  cin>>price[1]>>num[1];
  while(cin>>x>>y&&x!=-1&&y!=-1){
    while(x>price[m]+1){
        ++m;
        price[m]=price[m-1]+1;
        num[m]=num[m-1]+(y-num[m-1])/(x-price[m-1]);
        if(price[m]==a) n=num[m];
       // cout<<"*"<<price[m]<<" "<<num[m]<<endl;
    }
    price[++m]=x;
    num[m]=y;
    if(price[m]==a) n=num[m];
    maxprice=max(x,maxprice);
   // cout<<"*"<<price[m]<<" "<<num[m]<<endl;
  }
  int less;
  cin>>less;

  int j=maxprice+1;
  for(;;j++){
    if(num[m]-less<=0) break;
    price[++m]=j;
    num[m]=num[m-1]-less;
    if(price[m]==a) n=num[m];
   // cout<<"*"<<j<<" "<<num[m]<<endl;
  }
  int resMax=100000;
  int resMin=-100000;
  for(int i=1;i<=m;i++){
    if(price[i]==a) continue;
    double temp=1.0*((ll)price[i]*num[i]-a*n)/(n-num[i])+price[1];
      if(n>num[i]){
        resMin=max(resMin*1.0,ceil(temp));
      } 
      if(n<num[i]){
        resMax=min(resMax*1.0,floor(temp));
      }
  }
 // cout<<resMin<<"$ "<<resMax<<endl;
  if(resMin>resMax) cout<<"NO SOLUTION"<<endl;
  else if(resMin>0) cout<<ceil(resMin)<<endl;
  else if(resMax<0) cout<<floor(resMax)<<endl;
  else cout<<0<<endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}