EXAM-2018-8-9

水题 注意理解题意 有坑

博弈 观察发现 总是会进行到最后两个，或者先手取完全部，再特判一下只有一张牌的情况

九连环 通过找规律 我们可以得出递推式：

F[n]=F[n-1]+2*F[n-2]+1

而这个递推式可以通过构造矩阵，然后矩阵快速幂解决：

|F[n-1],F[n-2],1| * A = |F[n],F[n-1],1|

A=
1  1  0
2  0  0
1  0  1

初始矩阵为|2 1 1|

package hgf;
import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while (tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            } catch (Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if (hasNext())
            return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}

public class Main {
    static  InputReader cin=new InputReader();
        static PrintWriter cout=new PrintWriter(System.out);
    public static void main(String[] args) {
       int time,k;
       time=cin.nextInt();
       BigInteger arr[]=new BigInteger [3];
       BigInteger f[][]=new BigInteger [3][3];
      for(int z=1;z<=time;z++){
          k=cin.nextInt();
          if(k==1){
              System.out.println(1);
              continue;
          }
          if(k==2){
              System.out.println(2);
              continue;
          }
          arr[0]=B(2);arr[1]=B(1);
          arr[2]=B(1);
          f[0][0]=B(1);f[0][1]=B(1);f[0][2]=B(0);
          f[1][0]=B(2);f[1][1]=B(0);f[1][2]=B(0);
          f[2][0]=B(1);f[2][1]=B(0);f[2][2]=B(1);
          k=k-2;
          BigInteger c[]=new BigInteger [3];
          BigInteger d[][]=new BigInteger [3][3];
          for(;k!=0;k>>=1){
              if(k%2==1){
                    Arrays.fill(c, B(0));
                    for(int i = 0; i < 3; i++) {
                        for(int j = 0; j < 3; j++) {
                            c[i] = c[i].add(arr[j].multiply(f[j][i]));
                        }
                    }
                    for(int i = 0; i < 3; i++) {

                            arr[i] = c[i];
                    }

              }
              for(int i = 0; i < 3; i++) {
                    for(int j = 0; j < 3; j++) {
                         d[i][j]=B(0);
                    }
                }
              for(int i = 0; i < 3; i++) {
                    for(int j = 0; j < 3; j++) {
                        for(int p = 0; p < 3; p++) {
                            d[i][j] = d[i][j].add(f[i][p].multiply(f[p][j])) ;
                        }
                    }
                }
              for(int i = 0; i < 3; i++) {
                  for(int j = 0; j < 3; j++) {
                      f[i][j] = d[i][j];
                  }
              }
          }
          System.out.println(arr[0]);

      }
      cout.close();
    }
    static BigInteger B(int x) {
        return BigInteger.valueOf(x);
    }

}

BigInteger 申请1e5会超时

最讨厌看到有两个因素影响的题…..

题意是有l件衣服，m件洗衣机，n件烘干机,然后每件每次只能工作一件。然后这题是贪心做，最慢洗的配最快烘干的，然后肯定这几个机器是同时工作的，用d[i]维护一下。

单调队列的写法，注意一下。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7;
const int maxm=1e6+7;
ll l,n,m,w[maxn],d[maxn],t[maxm];
template<class T>
void read(T &res)
{
    res = 0;
    char c = getchar();
    T f = 1;
    while(c < '0' || c > '9')
    {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x >= 10)
    {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node{ll id;ll t;}u,v;
bool operator<(node a,node b){return a.t>b.t;}
priority_queue<node>x,h;
int main()
{
    read(l);
    read(n);
    read(m);
    for(int i=1;i<=n;i++){
        read(w[i]);
        u.id=i;
        u.t=w[i];
        x.push(u);
    }
    for(int i=1;i<=m;i++){
       read(d[i]);
        v.id=i;
        v.t=d[i];
        h.push(v);
    }
    for(int i=1;i<=l;i++){
        node q=x.top();
        x.pop();
        t[i]=q.t;
        ll ab=q.id;
        u.t=q.t+w[ab];
        u.id=q.id;
        x.push(u);
    }
    ll ans=0;
    for(int i=l;i>=0;i--){
        node q=h.top();
        h.pop();
        t[i]+=q.t;
        ll ab=q.id;
        v.t=q.t+d[ab];
        v.id=q.id;
        h.push(v);
        ans=max(ans,t[i]);
    }
   out(ans);
    return 0;
}

应该要特意总结一下的莫队算法。模板题。先分成sqtr(n)块，然后按块排序，而不是单纯先排左端点再排右端点。然后两个指针跳来跳去的看似暴力却不是暴力的算法。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
ll ans[maxn],ant;
int block,m,n,val[maxn],num[maxn],k;
struct node
{
    int l,r,id;
    inline bool operator <(node cmp) const {
       if(l/block!=cmp.l/block)
        return l/block<cmp.l/block;
       return r/block<cmp.r/block;
    }
}a[maxn];
void init()
{
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        val[i]^=val[i-1];
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d",&a[i].l,&a[i].r);
        a[i].l--;
        a[i].id=i;
    }
}
inline void add(int i)
{
    ant+=num[val[i]^k];
    num[val[i]]++;
}
inline void remov(int i)
{
    num[val[i]]--;
    ant-=num[val[i]^k];
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    block=sqrt(n);
    init();
    sort(a+1,a+n+1);
    ll l=1,r=0;
    for(int i=1;i<=m;i++){
        while(l>a[i].l){
            l--;
            add(l);
        }
        while(l<a[i].l){
            remov(l);
            l++;
        }
        while(r>a[i].r){
            remov(r);
            r--;
        }
        while(r<a[i].r){
            r++;
            add(r);
        }
        ans[a[i].id]=ant;
    }
    for(int i=1;i<=m;i++)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

北上广深算法？233333

裸模板题

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll g,p,m,a,b,n;
map <ll,ll> mp;
template<class T>
void read(T &res)
{
    res = 0;
    char c = getchar();
    T f = 1;
    while(c < '0' || c > '9')
    {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x >= 10)
    {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
int qpow(ll x,ll k)
{
    ll ans=1;
    while(k>0)
    {
        if(k&1)
            ans=(ans*x)%p;
        x=(x*x)%p;
        k>>=1;
    }
    return ans;
}
ll bsgs(ll x)
{
    ll j=0,cnt=1;
    for(; j<=m; ++j)
    {
        if(mp[(cnt*a)%p])
            return mp[(cnt*a)%p]-j;
        cnt=(cnt*g)%p;
    }
    return 0;
}
int main()
{
    ll i;
    read(g);
    read(p);
    m=ceil(sqrt(p));
    ll cnt=qpow(g,m),ans=cnt;
    mp[ans]=m;
    for(i=2;i<=m;++i)
    {
        ans=(ans*cnt)%p;
        mp[ans]=i*m;
    }
    read(n);
    while(n--)
    {
        read(a);
        read(b);
        out(qpow(b,bsgs(a)));
        printf("\n");
    }
    return 0;
}

地址EXAM-2018-8-9