学步园

A. Free cash

题目大意，输入第一行输入n，然后输入n行，每行输入两个数h 和 m ，要求把出现次数最多的h和m的次数输出。思路：此题运用哈希法，先令一个数tmp = h * 100 + m ，然后建立一个数组vis[2505],因为h <= 24 , m <= 60 ,所以tmp < 2505 ,最后用vis[tmp] ++ 来统计次数，找出vis数组中的最大值即可。

以下是代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std ;
const int MAXN = 2505 ;
int vis[MAXN] ;
int main()
{
    int n ;
    while (cin >> n)
    {
        memset(vis , 0 ,sizeof(vis)) ;
        int i ;
        int max = 0 ;
        for(i = 0 ; i < n ; i ++)
        {
            int h , m ;
            cin >> h >> m ;
            int tmp = h * 100 + m ;
            vis[tmp] ++ ;
            if(max < vis[tmp])
            {
                max = vis[tmp] ;
            }
        }
        printf("%d\n", max) ;
    }
    return 0 ;
}

B. Young Table

仔细读这道题才发现，原来题目中没有要求使操作的次数最少，只要完成就可以。此题麻烦了一些,请看代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std ;
const int MAXN = 55 ;
int s[MAXN][MAXN] ;
int t[MAXN * MAXN] ;
int t2[MAXN * MAXN] ;
int X1[MAXN * MAXN] ;
int Y1[MAXN * MAXN] ;
int X2[MAXN * MAXN] ;
int Y2[MAXN * MAXN] ;
struct Node
{
    int x ;
    int y ;
}vert[MAXN * MAXN] ;
int vis[MAXN * MAXN] ;
bool cmp(int a , int b)
{
    return a < b ;
}
int main()
{
    memset(s , 0 , sizeof(s)) ;
    int n ;
    scanf("%d" , &n) ;
    int i ;
    for( i = 0 ; i < n ; i ++)
    {
        scanf("%d" , &t[i]) ;
    }
    int j ;
    int cnt = 0 ;
    for(i = 0 ; i < n ; i ++)
    {
        for(j = 0 ; j < t[i] ; j ++)
        {
            scanf("%d" , &s[i][j]) ;
            int tmp  = s[i][j] ;
            vert[tmp].x = i + 1 ;
            vert[tmp].y = j + 1 ;
            t2[cnt ++] = s[i][j] ;
        }
    }
    sort(t2 , t2 + cnt , cmp) ;
    int sum = 0 ;
    int cnt2 = 0 ;
    for(i = 0 ; i < n ; i ++)
    {
        for(j = 0 ; j < t[i] ; j ++)
        {
            if(t2[cnt2] != s[i][j] )
            {
                int tx , ty ;
                tx = s[i][j] ;
                ty = t2[cnt2] ;
                X1[sum] = vert[tx].x ;
                Y1[sum] = vert[tx].y ;
                X2[sum] = vert[ty].x ;
                Y2[sum] = vert[ty].y ;
                int tp2 ;
                tp2 = s[i][j] ;
                s[i][j] = s[vert[ty].x - 1][vert[ty].y - 1] ; // 此处应注意不是s[vert[ty].x][vert[ty].y] ！！
                s[vert[ty].x - 1][vert[ty].y - 1] =tp2 ;

                tp2 = vert[tx].x ;
                vert[tx].x = vert[ty].x ;
                vert[ty].x = tp2 ;

                tp2 = vert[tx].y ;
                vert[tx].y = vert[ty].y ;
                vert[ty].y = tp2 ;

                sum ++ ;
            }
            cnt2 ++ ;
        }
    }
    printf("%d\n" , sum) ;
    for(i = 0 ; i < sum ; i ++)
    {
        printf("%d %d %d %d\n" , X1[i] , Y1[i] , X2[i] , Y2[i]) ;
    }
    return 0 ;
}

C.Primes on Interval

这道题一般的做法会超时，想了一会，有所改进，运用离线算法统计素数个数，结果还是超时，最后终于想到了二分，呵呵。请看代码：

#include<iostream>

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std ;
const int MAXN = 1000006 ;
int sushu[MAXN] ;
int sm[MAXN] ;
void prim()  // 素数表
{
    sushu[0] = 1 ;
    sushu[1] = 1 ;
    int i ;
    for(i = 2 ; i <= MAXN ; i ++)
    {
        int j ;
        if(sushu[i] == 0)
            for(j = 2 ; j * i <= MAXN ; j ++)
            {
                sushu[j * i] = 1 ;
            }
    }
}
void tong()
{
    int i ;
    int sumt = 0 ;
    for(i = 1 ; i <= MAXN ; i ++ )
    {
        if(sushu[i] == 0)
        {
            sumt ++ ;
        }
        sm[i] = sumt ;
    }
}
int main()
{
    int a , b , k ;
    prim() ;
    tong() ;
    while (scanf("%d%d%d" , &a , &b , &k) != EOF)
    {
        int pan = 0 ;
        int i ;
        int l ;
        int sum ;
        int left = 1 , right = b - a + 2 , mid ; // 这里right 必须比 b - a + 1 大一些，否则有错误。
        int pan2 = 0 ;
        while (left < right)  // 二分
        {
            mid = (left + right) / 2 ;
            int x ;
            int pan = 0 ;
            for(x = a ; x <= b - mid + 1 ; x ++)
            {
                sum = 0 ;
                //int tt = x + l - 1 ;
                sum = sm[x + mid - 1] - sm[x] ;
                if(sushu[x] == 0)
                    sum ++ ;
                //cout << "sum : " << sum << endl ;
                if(sum < k)
                {
                    pan = 1 ;
                    break ;
                }
            }
            if(pan == 0)
            {
                right = mid ;
                pan2 = 1 ;
            }
            else
            {
                left = mid + 1 ;
            }
        }
        if(pan2 == 0 )
            printf("-1\n") ;
        else
            printf("%d\n" , right) ;
    }
    return 0 ;
}

题目D很认真的读，就是读不懂，题目E暂时不会。