Android教程網 >> Android技術 >> 關於Android編程 >> Andrew Stankevich's Contest #補題

Andrew Stankevich's Contest #補題

編輯：關於Android編程

ACdream 1210 Chinese Girls' Amusement （規律+數學）

【題意】：

求最大的k<=n/2使得gcd(n,k)=1。

如果n是2m+1形式的，那麼k=m就是答案；
如果n是4m形式的，那麼k=2m-1就是答案；
如果n是4m+2形式的，那麼k=2m-1就是答案。
證明略，需要簡單的高精度。

java代碼：

//感覺就是暴力  從n/2 開始減 ，直到互素為止， 
import java.io.*;  
import java.util.*;  
import java.math.BigInteger;//聲明BigInteger大數類  
import java.lang.*;  

public class Main
{
	public static void main(String args[])
	{
		Scanner cin = new Scanner(System.in);
		BigInteger n,k;
		n=cin.nextBigInteger();
		k=n.divide(new BigInteger(2));
		while(n.gcd(k).compareTo(BigInteger.ONE)!=0)
		{
			k=k.subtract(BigInteger.ONE);
		}
		System.out.println(k);
	}
}

ACdream 1211 Reactor Cooling【上下界網絡流 + 輸出流量】

題意：

給n個點，及m根pipe，每根pipe用來流躺液體的，單向的，每時每刻每根pipe流進來的物質要等於流出去的物質，要使得m條pipe組成一個循環體，裡面流躺物質。

並且滿足每根pipe一定的流量限制，范圍為[Li,Ri].即要滿足每時刻流進來的不能超過Ri(最大流問題)，同時最小不能低於Li。

例如：

46(4個點，6個pipe)
12 1 3 (1->2上界為3，下界為1)
23 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3

可行流：

再如：所有pipe的上界為2下界為1的話，就不能得到一種可行流。

題解：

上界用ci表示，下界用bi表示。

下界是必須流滿的，那麼對於每一條邊，去掉下界後，其自由流為ci– bi。

主要思想：每一個點流進來的流=流出去的流

對於每一個點i，令

Mi= sum(i點所有流進來的下界流)– sum(i點所有流出去的下界流)

如果Mi大於0，代表此點必須還要流出去Mi的自由流，那麼我們從源點連一條Mi的邊到該點。

如果Mi小於0，代表此點必須還要流進來Mi的自由流，那麼我們從該點連一條Mi的邊到匯點。

如果求S->T的最大流，看是否滿流(S的相鄰邊都流滿)。

滿流則有解，否則無解。

代碼：

/*
*上下界的網絡流，用上界減去下界
* Problem: ACdream 1211
* Running time: 16MS
* Complier: G++
* Author: herongwei
* Create Time: 19:59 2015/10/8 星期四
*/
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;

const int N=250;
const int inf=0x3f3f3f3f;
#define clc(a,b) memset(a,b,sizeof(a));
struct node1
{
    int fm,to,cap,flow;
};
vector  v[N];
vector  e;
int vis[N],cnt[N];
void add_edge(int fm,int to,int cap)
{
    e.push_back((node1){fm,to,cap,0});
    e.push_back((node1){to,fm,0,0});
    int tmp=e.size();
    v[fm].push_back(tmp-2);
    v[to].push_back(tmp-1);
}
bool bfs(int s,int t)
{
    clc(vis,-1);
    queue q;
    q.push(s);
    vis[s] = 0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=0;itmp.flow)  //第二個條件保證
            {
                vis[tmp.to]=vis[x]+1;
                q.push(tmp.to);
            }
        }
    }
    if(vis[t]>0)return true;
    return false;
}
int dfs(int o,int f,int t)
{
    if(o==t || f==0)  //優化
        return f;
    int a = 0,ans=0;
    for(int &i=cnt[o];i0)
        {
            tmp.flow+=a;
            e[v[o][i]^1].flow-=a; //存圖方式
            ans+=a;
            f-=a;
            if(f==0)  //注意優化
                break;
        }
    }
    return ans;  //優化
}
int dinic(int s,int t)
{
    int ans=0;
    while(bfs(s,t))
    {
        clc(cnt,0);
        int f=dfs(s,inf,t);
        ans+=f;
    }
    return ans;
}

int come[N],to[N];
int flow[N][N];
struct node2
{
    int x,y;
} num[N*N];
void init(int n)
{
     for(int i=0;i<=n;i++)
        v[i].clear();
    e.clear();
}
int main()
{
    //freopen(1.txt,r,stdin);
    int _,__;
    while(~scanf(%d%d,&_,&__))
    {
        clc(come,0);
        clc(to,0);
        clc(flow,0);
        int s=0,t = _+1;
        for(int i=0;i<__;i++)
        {
            int x,y,mi,ma;
            scanf(%d%d%d%d,&x,&y,&mi,&ma);
            num[i] = (node2){x,y};
            flow[x][y] += mi;
            add_edge(x,y,ma-mi);
            come[x]+= mi;
            to[y] += mi;
        }
        int s2=0;
        for(int i=1;i<=_;i++)
        {
            int tmp = come[i]-to[i];
            if(tmp<0)
            {
                s2+=(-tmp);
                add_edge(s,i,-tmp);
            }
            if(tmp>0) add_edge(i,t,tmp);
        }
        int ans = dinic(s,t);
        if(ans != s2)
            puts(NO);
        else
        {
            puts(YES);
            for(int i=1;i<=_;i++)
            {
                for(int j=0;j

ACdream 1213  Matrix Multiplication （數學）

【題意】： 
A是圖G的關聯矩陣，求B=A^TA的元素和。
其實就是統計每個數的個數，最後平方求和
代碼：
 
/*
* this code is made by herongwei
* Problem: 1213
* Verdict: Accepted
* Submission Date: 2015-10-06 21:11:02
* Time: 76MS
* Memory: 1712KB
*/
 
#include 
using namespace std;
int arr[10005];
int main()
{
    int n,m;cin>>n>>m;
    memset(arr,0,sizeof(arr));
    for(int i=0; i>u>>v;
        arr[u]++;
        arr[v]++;
    }
    int s=0;
    for(int i=1; i<=n; ++i)
        s+=arr[i]*arr[i];
    cout<

ACdream 1216 Beautiful People（二路單調LIS） 
【題意】：
 

選取最多的人，要求不存在兩個人i和j，Si <= Sj && Bi >= Bj。
 

【思路】先把所有人按S升序排序，然後再按B降序排序，對B求最長上升子序列(LIS)。LIS是很經典的問題了，簡單的DP復雜度問O(n^2)，這裡需要使用經典的O(nlg(n))的算法。

代碼：
 
/*
* this code is made by herongwei
* Problem: 1216
* Verdict: Accepted
* Submission Date: 2015-10-08 20:39:41
* Time: 132MS
* Memory: 3632KB
*/
#include 
#include 
#include 
#include 
using namespace std;

const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
struct node
{
    int x,y,id;
    bool operator <(const node &t) const
    {
        if(x!=t.x) return xt.y;
    }
} st[maxn];
int dp[maxn];//dp[i]表示最長上升子序列長度為i時子序列末尾的最小B值
int LIS[maxn];//LIS[i]表示以第i個people結尾的最長上升子序列的長度
int main()
{
    //freopen(1.txt,r,stdin);
    int _;
    while(~scanf(%d,&_))
    {
        memset(dp,inf,sizeof(dp));
        memset(LIS,0,sizeof(LIS));
        for(int i=1; i<=_; ++i)
        {
            scanf(%d%d,&st[i].x,&st[i].y);
            st[i].id=i;
        }
        sort(st+1,st+_+1);
        int len=1,ans=1;
        for(int i=1; i<=_; ++i)
        {
            int ck=lower_bound(dp+1,dp+len+1,st[i].y)-dp;//返回大於或等於val的第一個元素位置；
            if(ck==len) len++;
            dp[ck]=st[i].y;
            LIS[i]=ck;
            ans=max(ans,ck);
          //  cout<=1; --i)
        {
            if(LIS[i]==ans)
            {
                printf(%d,st[i].id);
                if(len!=1) printf( );
                ans--;
            }
        }
        puts();
    }
    return 0;
}

 
ACdream 1427 Nice Sequence
【題意】：
 
E - Nice Sequence
Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others) Submit Status
Problem Description
Let us consider the sequence a1, a2,..., an of non-negative integer numbers. Denote as ci,j the number of occurrences of the number i among a1,a2,..., aj. We call the sequence k-nice if for all i1 
Given the sequence a1,a2,..., an and the number k, find its longest prefix that is k-nice.
Input
The first line of the input file contains n and k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 200 000). The second line contains n integer numbers ranging from 0 to n.
Output
Output the greatest l such that the sequence a1, a2,..., al is k-nice.
Sample Input
10 1
0 1 1 0 2 2 1 2 2 3
2 0
1 0

Sample Output
8
0
【題意】這道題理解題意很重要， 其實就是當我們從左向右輸入一個元素x時，要保證其左側元素中0-（x-1）出現的次數大於等於 x的出現次數-k，找出這樣的最長的前綴。
 
【思路】：每次輸入一個元素，要更新它的次數，還要比較前（x-1）個出現次數的最小值，因此可用線段樹維護最小值。只要判斷當前x的次數和（前x-1）的次數最小值比較小於K，則break,否則輸出查找的最長前綴。
代碼：
/*
* 線段樹 單點更新，單點查詢
* Problem: ACdream No.1427
* Running time: 252MS
* Complier: G++
* Author: javaherongwei
* Create Time: 21:00 2015/10/7
*/
#include 
#include 
#include 
#include 

using namespace std;
const int maxn=200010;
const int inf=0x3f3f3f3f;
inline int max(int a,int b) {return a>b?a:b;}
inline int min(int a,int b) {return a>1;
    }
}tree[maxn<<2];
int n,k,sum[maxn<<2];
int arr[maxn],A[maxn];
void build(int l,int r,int rt)
{
    tree[rt].left=l;
    tree[rt].right=r;
    tree[rt].minv=tree[rt].maxv=0;
    if(l==r) return ;
    int m=tree[rt].mid();
    build(l,m,rt*2);
    build(m+1,r,rt*2+1);
}
void update(int pos,int add,int rt)
{
    int l=tree[rt].left;
    int r=tree[rt].right;
    if(l==r)
    {
      tree[rt].minv+=add;
      return ;
    }
    int m=tree[rt].mid();
    if(m>=pos) update(pos,add,rt*2);
    else update(pos,add,rt*2+1);
    tree[rt].minv=min(tree[rt*2].minv,tree[rt*2+1].minv);
}
int query_min(int ql,int qr,int rt)//query(0,arr[ii]-1,1)
{
    int l=tree[rt].left;
    int r=tree[rt].right;
    if(ql<=l&&r<=qr)
    {
        return tree[rt].minv;
    }
    int m=tree[rt].mid();
    int ans1,ans2;
    if(m>=qr)  return query_min(ql,qr,rt<<1);
    else if(m

 
ACdream 1431 Sum vs Product 【題意】：求固定長度為n（2=2)，必然出現這麼一個集合{1,1,1,,,,2*n}內 如： n

3 {1,2,3}

4 {1,1,2,4}

5 {1,1,1,2,5} {1,1,2,2,2} {1,1,1,3,3}

。。。 集合最大元素必然不超過n,因此後面的元素從n依次遞減到2，因此要滿足條件，必須要1來補充，發現假如全部填2，則最多填2^9=512>500,即9個2 對於數據范圍，可以考慮暴搜 代碼：
/*
* DFS
* Problem: ACdrema No.1431
* Running time: 0MS
* Complier: G++
* Author: javaherongwei
* Create Time: 21:00 2015/10/7
*/
#include 
#include 
#include 
#include 
using namespace std;
int n,sum;
// 當前可枚舉的最大值，深度，當前積，當前和
//剪枝：當前積小於當前和加當前長度則繼續搜索
void dfs(int cur,int now_ji,int now_he,int depth){
    for(int i=cur; i>=2; --i){
        if(depth>n) break;
        if(now_ji*i==(now_he+i+n-depth)) sum++;
        else if(now_ji*i<(now_he+i+n-depth))
            dfs(i,now_ji*i,now_he+i,depth+1);
    }
}
int main(){
    while(~scanf(%d,&n)){
        sum=0;
        dfs(n,1,0,1);
        printf(%d
,sum);
    }
    return 0;
}

上一頁:Android性能專項測試之Batterystats
下一頁:android開發之使用拼音搜索漢字

關於Android編程

Android編程入門 Android技術基礎 Android資訊關於Android編程 Android開發 Android開發環境 Android開發實例

相關文章

Andrew Stankevich&#39;s Contest #補題

E - Nice Sequence

Problem Description

Input

Output

Sample Input

Sample Output

Andrew Stankevich's Contest #補題