程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BNU Training 2015 07 27 題解

BNU Training 2015 07 27 題解

編輯：關於C++

uva 12435 C. Consistent Verdicts

【題目大意】：給你二維平面一些人的坐標，每個人手上都有一把槍，求全部人同時開槍後所有人聽到槍聲的次數的可能數目。

【解題思路】：O(n^2)暴力枚舉+unique 函數去重相鄰元素。居然只跑了3ms，~~

代碼：

// C
#ifndef _GLIBCXX_NO_ASSERT
#include 
#endif

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

// C++
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))

typedef long long LL;
typedef unsigned long long LLU;
typedef double db;
const int N=1e6+10;
const int inf=0x3f3f3f3f;

char str[N];
bool vis[N];

int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};

inline LL read()
{
    int c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        c=c*10+ch-'0';
        ch=getchar();
    }
    return c*f;
}

char mon1[N],mon2[N];
LL day1,year1;
LL day2,year2;
LL row,line,x,t,y,i,res;

struct node
{
    LL codrx;
    LL codry;
};
node num[N];
LL mum[N];
int main()
{
    LL tot=1;
    t=read();
    while(t--){
        x=read();
        int len=0;
        for(i=0; i

uva 12439 G. February 29

【題目大意】兩個日期之間求leap data的個數：ps:常規方法判斷會TE，因此換個思路，判斷閏年可以用除法代碼：

// C
#ifndef _GLIBCXX_NO_ASSERT
#include 
#endif

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

// C++
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))

typedef long long LL;
typedef unsigned long long LLU;
typedef double db;
const int N=1e5;
const int inf=0x3f3f3f3f;

char str[N];
bool vis[N];

int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};

bool leap_year(int y)
{
    if(y%4==0&&y%100!=0||y%400==0) return 1;
    return 0;
}
inline LL read()
{
    int c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        c=c*10+ch-'0';
        ch=getchar();
    }
    return c*f;
}

char mon1[N],mon2[N];
LL day1,year1;
LL day2,year2;
LL row,line,x,t,y,i,res;

int main()
{
    scanf(%lld,&t);
    for(i=1; i<=t; ++i)
    {
        int res=0;
        scanf(%s %lld,%lld,mon1,&day1,&year1);
        scanf(%s %lld,%lld,mon2,&day2,&year2);
        if((mon1[0]=='J'&&mon1[1]=='a')||mon1[0]=='F') year1=year1;
        else year1++;
        if((mon2[0]=='J'&&mon2[1]=='a')||mon2[0]=='F'&&day2<=28) year2--;
        res=(year2/4)-((year1-1)/4);
        res=res-(year2/100)+((year1-1)/100);
        res=res+(year2/400)-((year1-1)/400);
        printf(Case %lld: %lld
,i,res);
    }
    return 0;
}

uva 12442 J. Forwarding Emails

【題目大意】：酋長發一封信給部落的人，給出部落的人的關系，沒人只能收一次且發一次，求在信能傳遞的最長的的人數鏈的情況下第一次收到信的人的編號【解題思路】：網上看到一個比較直觀的思路過程，復制過來，便於理解： Solution Description :

DFS problem
Read this line carefully in problem description - they each pick one other person they know to email those things to every time - exactly one, no less, no more (and never themselves) i.e Each person send email only one. For each person has only one adjacency person. The input can not be (1 to 3, 2 to 3, 1 to 2) , because for person 1 here 2 adjacency person 3 and 2. So, you can represent this graph using one dimensional array adj[N]. Do not need to stack, you can use recursion.
Example:

1 2

2 1

4 3

3 2

The adjacency list, adj[1]=2, adj[2]=1, adj[3]=2, and adj[4]=3.

Use a boolean array visit[N]

visit[1]

visit[2]

visit[3]

visit[4]

False

At first start from 1

If visit[1]==false then run DFS in this time count the visited node and update the visit[] array 
(Set visit[i]=True here i is a visited node).  
Remember dot not use the array visit[] for cycle finding you can use another boolean array visit2[] for that purpose. 
After run DFS the visit[] array is

visit[1]

visit[2]

visit[3]

visit[4]

True

False

And count_visited_node=2 (1->2)

Now 2

visit[2]==true so, do not need to do anything.

Now 3

visit[3]==false so, run the DFS. After that the visit[] array is

visit[1]

visit[2]

visit[3]

visit[4]

True

False

And count_visited_node=3 (3->2->1)

Now 4

visit[4]==false so, run the DFS. After that the visit[] array is

visit[1]

visit[2]

visit[3]

visit[4]

True

And count_visited_node=4 (4->3->2->1)

For 4, the count_visited_node is maximum. Ans is 4.

代碼：

#include 
#define MAX 50005
int T,N;
int vis[MAX], f[MAX], c[MAX];
int ans, flag;
typedef long long LL;

inline LL read()
{
    int c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    return c*f;
}

int dfs(int u)
{
    int v = f[u];/// 2=f[1];1=f[2];2=f[3];
    int r = 0;   ///
    vis[u] = 1;  /// vis[1]=1;vis[2]=1;vis[3]=1;
    if(!vis[v]) r = dfs(v) + 1;///vis[2]=1,r=0+1=1;
    vis[u] = 0;
    c[u] = r;   ///c[1]=1,c[2]=0,c[3]=2;
    return r;
}

int main()
{
    int u,v;
    T=read();
    for(int t=1; t<=T; t++){
        N=read();
        for(int i=1; i<=N; i++){
            u=read(),v=read();
            f[u] = v;
            vis[u] = 0;
            c[u] = -1;
        }
        ans = -1;
        for(int i=1; i<=N; i++){
            if(c[i]==-1) dfs(i);
            if(c[i]>m)
            {
                m=c[i];
                flag=i;
            }
          /*  printf(vertex %d children %d
,i,c[i]);*/
        }
        printf(Case %d: %d
,t,flag);
    }
    return 0;
}

幾組數據：

Case 1: 1
Case 2: 4
Case 3: 3
Case 4: 1
Case 5: 1
Case 6: 4
Case 7: 1

上一頁:POJ 2417/BZOJ 3239(Discrete Logging
下一頁:HDU 4293 Groups（區間dp）

關於C++

OpenCV——PS濾鏡算法之球面化代碼 (凹陷效果)

// define head function#ifndef

c++跨平台技術學習(一)

引言能被不同平台共享的代碼越多，跨平台的項目就越容易。所有平

C++中的名字查找問題解答

朋友最近發郵件問我兩個問題。內容如下（為了更適

opencv小練習：哈爾小波(Haar)

首先說一下一維haar小波的原理。例如我們有一個一維的圖像[

Qt小游戲開發：掃雷

繼續把Qt小游戲寫一下~預覽步驟整體的代碼結構，

poj 1251 Jungle Roads

Jungle RoadsTime Limit : 2000/

熱門圖文

GraPHPite--PHP圖像庫新秀 dll生成-想用MFC生成.dll物件，lib和ilk文件是否可以扔了給網站加上google的reCAPTCHA驗證碼加強驗證 EJB 3.0注入(會話BEAN) windows-請教下大神們，VC＋＋怎麼創建虛擬設備？如圖： Delphi編程的優秀輔助工具-GExperts php隨機取mysql記錄方法小結，phpmysql記錄小結【Java每日一題】20161101，java20161101

欄目導航

C++基礎知識 C++入門知識關於C++