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

链接:洛谷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;
}

题目链接:CH4201

对某个点,求前面和后面分别有多少个点的纵坐标是比它大的,两数相乘就是以该点为中间点,能构成的"v"的数量.

"^"同理.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

#define maxn 200005

typedef long long ll;
typedef unsigned long long ull;

int c[maxn];
int a[maxn];
int Right1[maxn];
int Left1[maxn];
int Right2[maxn];
int Left2[maxn];
int n;

int ask(int x){
  int ans=0;
  for(;x;x-=x&-x) ans+=c[x];
  return ans;
}

void add(int x,int y){
  for(;x<=n;x+=x&-x) c[x]+=y;
}

int main() {
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  for(int i=n;i>0;--i){
      Right1[i]=n-i-ask(a[i]);
      Right2[i]=ask(a[i]-1);
      add(a[i],1);
  }
  memset(c,0,sizeof(c));
  for(int i=1;i<=n;++i){
    Left1[i]=i-1-ask(a[i]);
    Left2[i]=ask(a[i]-1);
    add(a[i],1);
  }
  ll ans1=0,ans2=0;

  for(int i=1;i<=n;++i){
    ans1+=(ll)Left1[i]*Right1[i];
    ans2+=(ll)Left2[i]*Right2[i];
  } 
  cout<<ans1<<" "<<ans2<<endl;
  return 0;
}

题目链接:BZOJ 4195

在数据范围大,但实际数据个数不大的时候,采用离散化避免超出数组空间.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

#define maxn 1000005

typedef long long ll;
typedef unsigned long long ull;

int fa[maxn * 2];

int x1[maxn];
int x2[maxn];
int s[maxn];
int n;
vector<int> b;

void init() {
  b.clear();
  for (int i = 0; i <= 2 * n; ++i) {
    fa[i] = i;
  }
}

int get(int x) {
  if (x == fa[x]) return x;
  return fa[x] = get(fa[x]);
}

void merge(int x, int y) { fa[get(x)] = get(y); }

void discrete() {
  sort(b.begin(), b.end());
  unique(b.begin(), b.end());
}
int query(int x) { return lower_bound(b.begin(), b.end(), x) - b.begin(); }

int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    init();
    for (int k = 1; k <= n; ++k) {
      cin >> x1[k] >> x2[k] >> s[k];
      b.push_back(x1[k]);
      b.push_back(x2[k]);
    }
    discrete();
    for (int i = 1; i <= n; ++i) {
      if (s[i]) {
        int x = query(x1[i]);
        int y = query(x2[i]);
        merge(x, y);
      }
    }
    int flag = 0;
    for (int i = 1; i <= n; ++i) {
      if (!s[i]) {
        int x = query(x1[i]);
        int y = query(x2[i]);
        if (get(x) == get(y)) {
          cout << "NO" << endl;
          flag = 1;
          break;
        }
      }
    }
    if (!flag) {
      cout << "YES" << endl;
    }
  }
  return 0;
}

题目链接:CH3601

通过逆元计算组合数.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int quickpow(int m,int n,int mod){
  int res=1;
  while(n){
    if(n&1) res=(ll)res*m%mod;
    m=(ll)m*m%mod;
    n>>=1;
  }
  return res;
}

int factorial(int n,int mod){
      if(!n) return 1;
      int res=n%mod;
      while(--n){
        res=(ll)res*n%mod;
      }
      return res;
}

int main() {
  int a,b,n,m,k;
  const int mod=10007;
  cin>>a>>b>>k>>n>>m;
  a=quickpow(a,n,mod);
  b=quickpow(b,m,mod);
  int x=factorial(k,mod);
  int y1=factorial(n,mod);
  int y2=factorial(k-n,mod);
  y1=quickpow(y1,mod-2,mod);
  y2=quickpow(y2,mod-2,mod);
  int ans=(ll)y1*y2%mod*x%mod*a%mod*b%mod;
  cout<<ans<<endl;
  return 0;
}

题目链接：POJ1845

题意:求\(A^B\)的所有约数之和\(\mod 9901\), \(1 \le A,B \le 5*10^7 \).

把A分解质因数,可以得到约数和为:
\((1+p_1+p_1^2+...+p_1^{B*c_1})*(1+p_2+p_2^2+...+p_2^{B*c_2})*...*(1+p_n+p_n^2+...+p_n^{B*c_n})\)

其中每一项都是等比数列求和:\( \frac{p_i^{B*c_i+1}-1}{p_i-1}\),如果分母逆元存在,则用乘以逆元代替除法运算,如果不存在,有\(p_i\mod 9901=1\),则:
\( 1+p_i+p_i^2+...+p_i^{B*c_i}\equiv 1+1+1^2+...+1^{B*c_i}\equiv B*c_i+1 \pmod {9901} \).

code：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int c[20],p[20];
int m;
void divide(int a){
    m=0;
    for(int i=2;i<=sqrt(a);++i){
      if(a%i==0){
        p[++m]=i;
        c[m]=0;
        while(a%i==0){
          a/=i;
          c[m]++;
        }
      }
    }
    if(a>1){
      p[++m]=a;
      c[m]=1;
    }
}

int quickpow(int mod,int a,int n){
  int res=1;
  while(n){
    if(n&1) res=(ll)res*a%mod;
    a=(ll)a*a%mod;
    n>>=1;
  }
  return res;
}

int inv(int mod,int x){
  return quickpow(mod,x,mod-2);
}

int main(){
  int a,b;
  const int mod=9901;
  cin>>a>>b;
  divide(a);
  int ans=1;
  for(int i=1;i<=m;++i){
    int x=(quickpow(mod,p[i],(ll)b*c[i]+1)-1+mod)%mod;
    int y=(p[i]-1)%mod;
    if(y){
      ans=(ll)ans*(x*inv(mod,y))%mod;
    }
    else{
      ans=ans*((ll)b*c[i]+1)%mod;  
    }
  }
  cout<<ans<<endl;
  return 0;
}