2017 ACM/ICPC Asia Regional Shenyang Online总结 5/11

B - cable cable cable

  HDU - 6195 

Connecting the display screen and signal sources which produce different color signals by cables, then the display screen can show the color of the signal source.Notice that every signal source can only send signals to one display screen each time. 
Now you have  M M display screens and  K K different signal sources( K≤M≤232−1 K≤M≤232−1). Select  K K display screens from  M M display screens, how many cables are needed at least so that **any**  K K display screens you select can show exactly  K K different colors. 

Input

Multiple cases (no more than  100 100), for each test case: 
there is one line contains two integers  M M and  K K. 

Output

Output the minimum number of cables  N N. 

Sample Input

3 2
20 15

Sample Output

4
90

        
  

Hint

         
  
   
   
    
  
  
As the picture is shown, when you select M1 and M2, M1 show the color of K1, and M2 show the color of K2.

When you select M3 and M2, M2 show the color of K1 and M3 show the color of K2.

When you select M1 and M3, M1 show the color of K1.


        
 

推公式题目：

ans = (ll)k*(m-(k-1));

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  vector<int> vi;
typedef  long long ll;
typedef  unsigned long long  ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int T;
int m,k;
ll ans = 0;
int main() {
//    freopen("data.txt","r",stdin);
//    scanf("%d",&T);
    while(~scanf("%d %d",&m,&k))
    {
        ans = (ll)k*(m-(k-1));
        printf("%lld\n",ans);
    }
}

D - array array array

  HDU - 6197 

One day, Kaitou Kiddo had stolen a priceless diamond ring. But detective Conan blocked Kiddo's path to escape from the museum. But Kiddo didn't want to give it back. So, Kiddo asked Conan a question. If Conan could give a right answer, Kiddo would return the ring to the museum. 
Kiddo: "I have an array  A A and a number  k k, if you can choose exactly  k k elements from  A A and erase them, then the remaining array is in non-increasing order or non-decreasing order, we say  A A is a magic array. Now I want you to tell me whether  A A is a magic array. " Conan: "emmmmm..." Now, Conan seems to be in trouble, can you help him? 

Input

The first line contains an integer T indicating the total number of test cases. Each test case starts with two integers  n n and  k k in one line, then one line with  n n integers:  A1,A2…An A1,A2…An. 
1≤T≤20 1≤T≤20 
1≤n≤105 1≤n≤105 
0≤k≤n 0≤k≤n 
1≤Ai≤105 1≤Ai≤105 

Output

For each test case, please output "A is a magic array." if it is a magic array. Otherwise, output "A is not a magic array." (without quotes). 

Sample Input

3
4 1
1 4 3 7
5 2
4 1 3 1 2
6 1
1 4 3 5 4 6

Sample Output

A is a magic array.
A is a magic array.
A is not a magic array.

求一遍最长递增子序列和一次最长递减zi

最长递增子序列的O(n*log(n))的做法

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  vector<int> vi;
typedef  long long ll;
typedef  unsigned long long  ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int getLISLength(vector<int> num, int length) {
    vector<int> ivec;
    for(int i = 0; i < length; ++i)
        {
    if (ivec.size() == 0 || ivec.back() < num[i])
        ivec.push_back(num[i]);
    else {
int low = 0, high = ivec.size() - 1;
 while (low < high) {
int mid = (low + high) / 2;
if (ivec[mid] < num[i])
low = mid + 1;
else
high = mid - 1;
}
ivec[low] =num[i];
}
}
return ivec.size();
}

int T;
int n,k,t;
vector<int> a;

int main() {
//    freopen("data.txt","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        a.clear();
        scanf("%d %d",&n,&k);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&t);
            a.push_back(t);
        }
        int ans = 0;
        ans = getLISLength(a,n);
        reverse(a.begin(),a.end());
        ans = max(getLISLength(a,n),ans);
        ans = n-ans;

        if(k>=ans)
        {
            printf("A is a magic array.\n");
        }
        else
        {
            printf("A is not a magic array.\n");
        }

    }
}

E - number number number

  HDU - 6198 

We define a sequence  F F: 

⋅ ⋅  F0=0,F1=1 F0=0,F1=1; 
⋅ ⋅  Fn=Fn−1+Fn−2 (n≥2) Fn=Fn−1+Fn−2 (n≥2). 

Give you an integer  k k, if a positive number  n n can be expressed by 
n=Fa1+Fa2+...+Fak n=Fa1+Fa2+...+Fak where  0≤a1≤a2≤⋯≤ak 0≤a1≤a2≤⋯≤ak, this positive number is  mjf−good mjf−good. Otherwise, this positive number is  mjf−bad mjf−bad. 
Now, give you an integer  k k, you task is to find the minimal positive  mjf−bad mjf−bad number. 
The answer may be too large. Please print the answer modulo 998244353. 

Input

There are about 500 test cases, end up with EOF. 
Each test case includes an integer  k k which is described above. ( 1≤k≤109 1≤k≤109) 

Output

For each case, output the minimal  mjf−bad mjf−bad number mod 998244353. 

Sample Input

1

Sample Output

4

首先DFS打表找规律，然后利用矩阵快速幂加速的快速斐波那契

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  vector<int> vi;
typedef  long long ll;
typedef  unsigned long long  ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};


const int MOD = 998244353;

struct matrix {     //矩阵
    long long m[2][2];
}ans;

matrix base = {1, 1, 1, 0};

matrix multi(matrix a, matrix b) {  //矩阵相乘，返回一个矩阵
    matrix tmp;
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            tmp.m[i][j] = 0;
            for(int k = 0;  k < 2; k++)
                tmp.m[i][j] = (tmp.m[i][j] + (a.m[i][k]%MOD) * (b.m[k][j]%MOD)%MOD ) % MOD;
        }
    }
    return tmp;
}

ll matrix_pow(matrix a, ll n) {   //矩阵快速幂，矩阵a的n次幂
    ans.m[0][0] = ans.m[1][1] = 1;  //初始化为单位矩阵
    ans.m[0][1] = ans.m[1][0] = 0;
    while(n) {
        if(n & 1) ans = multi(ans, a);
        a = multi(a, a);
        n >>= 1;
    }
    return ans.m[0][1];
}

int T;
ll n;
int main() {
//    freopen("data.txt","r",stdin);
//    scanf("%d",&T);
    while(~scanf("%lld",&n))
    {
        printf("%lld\n", matrix_pow(base, n*2+3)-1);

    }

}

H - transaction transaction transaction

 

Kelukin is a businessman. Every day, he travels around cities to do some business. On August 17th, in memory of a great man, citizens will read a book named "the Man Who Changed China". Of course, Kelukin wouldn't miss this chance to make money, but he doesn't have this book. So he has to choose two city to buy and sell. 
As we know, the price of this book was different in each city. It is  ai ai  yuan yuan in  i i t t city. Kelukin will take taxi, whose price is  1 1 yuan yuan per km and this fare cannot be ignored. 
There are  n−1 n−1 roads connecting  n n cities. Kelukin can choose any city to start his travel. He want to know the maximum money he can get. 

Input

The first line contains an integer  T T ( 1≤T≤10 1≤T≤10) , the number of test cases. 
For each test case: 
first line contains an integer  n n ( 2≤n≤100000 2≤n≤100000) means the number of cities; 
second line contains  n n numbers, the  i i th th number means the prices in  i i th th city;  (1≤Price≤10000) (1≤Price≤10000) 
then follows  n−1 n−1 lines, each contains three numbers  x x,  y y and  z z which means there exists a road between  x x and  y y, the distance is  z z km km  (1≤z≤1000) (1≤z≤1000). 

Output

For each test case, output a single number in a line: the maximum money he can get. 

Sample Input

1  
4  
10 40 15 30  
1 2 30
1 3 2
3 4 10

Sample Output

8

树上的DP，每一个数，求该点能得到的最小值

dfs直接遍历一遍，时间复杂度为O(n)

这儿还有一个最长路实现的算法。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
 #include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  vector<int> vi;
typedef  long long ll;
typedef  unsigned long long  ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int N = 1e5+5;

struct node{
    int to;
    int len;
};
\

int dp[N];
vector<node> a[N];
int val[N];
int x,y,z;
int vis[N];
int n;
int T;

int dfs(int cur)
{
    if(vis[cur]) return dp[cur];
    vis[cur] = 1;
    for(int i=0;i<a[cur].size();i++)
    {
        dp[cur] = min( dp[cur] , dfs(a[cur][i].to)+a[cur][i].len );
    }
    return dp[cur];
}



int main() {
//    freopen("data.txt","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        node nt;
        scanf("%d",&n);
        for(int i=0;i<=n;i++)
        {
            a[i].clear();
        }
        memset(vis,0,sizeof(vis));


        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
            dp[i] = val[i];
        }

        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            nt.to = y;
            nt.len = z;
            a[x].push_back(nt);
            nt.to = x;
            a[y].push_back(nt);
        }

        dfs(1);

        int ans = 0;
        for(int i=1;i<=n;i++)
        {
            ans = max(ans,val[i]-dp[i]);
        }
        printf("%d\n",ans);
    }
}

L - card card card

  HDU - 6205 

As a fan of Doudizhu, WYJ likes collecting playing cards very much. 
One day, MJF takes a stack of cards and talks to him: let's play a game and if you win, you can get all these cards. MJF randomly assigns these cards into  n n heaps, arranges in a row, and sets a value on each heap, which is called "penalty value". 
Before the game starts, WYJ can move the foremost heap to the end any times. 
After that, WYJ takes the heap of cards one by one, each time he needs to move all cards of the current heap to his hands and face them up, then he turns over some cards and the number of cards he turned is equal to the  penaltyvalue penaltyvalue. 
If at one moment, the number of cards he holds which are face-up is less than the  penaltyvalue penaltyvalue, then the game ends. And WYJ can get all the cards in his hands (both face-up and face-down). 
Your task is to help WYJ maximize the number of cards he can get in the end.So he needs to decide how many heaps that he should move to the end before the game starts. Can you help him find the answer? 
MJF also guarantees that the sum of all "penalty value" is exactly equal to the number of all cards. 

Input

There are about  10 10 test cases ending up with EOF. 
For each test case: 
the first line is an integer  n n ( 1≤n≤106 1≤n≤106), denoting  n n heaps of cards; 
next line contains  n n integers, the  i i th th integer  ai ai ( 0≤ai≤1000 0≤ai≤1000) denoting there are  ai ai cards in  i i th thheap; 
then the third line also contains  n n integers, the  i i th th integer  bi bi ( 1≤bi≤1000 1≤bi≤1000) denoting the "penalty value" of  i i th th heap is  bi bi. 

Output

For each test case, print only an integer, denoting the number of piles WYJ needs to move before the game starts. If there are multiple solutions, print the smallest one. 

Sample Input

5
4 6 2 8 4
1 5 7 9 2

Sample Output

4

        
  

Hint

[pre]
For the sample input:

+ If WYJ doesn't move the cards pile, when the game starts the state of cards is:
	4 6 2 8 4
	1 5 7 9 2
WYJ can take the first three piles of cards, and during the process, the number of face-up cards is 4-1+6-5+2-7. Then he can't pay the the "penalty value" of the third pile, the game ends. WYJ will get 12 cards.
+ If WYJ move the first four piles of cards to the end, when the game starts the state of cards is:
	4 4 6 2 8
	2 1 5 7 9
WYJ can take all the five piles of cards, and during the process, the number of face-up cards is 4-2+4-1+6-5+2-7+8-9. Then he takes all cards, the game ends. WYJ will get 24 cards.

It can be improved that the answer is 4.

**huge input, please use fastIO.**
[/pre]

        
 

可以考虑一下贪心的做法，然后用双指针扫描就OK啦

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1

using namespace std;
typedef  vector<int> vi;
typedef  long long ll;
typedef  unsigned long long  ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int maxn=1e6+10;


int T;
int n;
int a[maxn];
int b[maxn];

int main() {
//    freopen("data.txt","r",stdin);
//    scanf("%d",&T);
    while(~scanf("%d",&n))
    {
        int ans = 0;
        ll ansx=-1;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d",&b[i]);
        }
        for(int i=0;i<n;i++)
        {
            b[i] = a[i]-b[i];
        }

        for(int i = 0 ;i < n;)
        {
            ll sum = b[i];
            ll re  = a[i];
            int j = (i+1)%n;
            while(sum>=0&&j!=i)
            {
                re +=a[j];
                sum+=b[j];
                j++;
                j%=n;
            }

            if(re>ansx)
            {
                ansx=re;
                ans = i;
            }
            if(j<=i) break;
            i=j;
        }

        printf("%d\n", ans);
    }

}