程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #271 (Div. 2) 解題報告

Codeforces Round #271 (Div. 2) 解題報告

編輯：C++入門知識

Codeforces Round #271 (Div. 2) 解題報告

A題：Keyboard

模擬水題。

代碼如下：

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

using namespace std;
#define LL __int64
char s[]={qwertyuiopasdfghjkl;zxcvbnm,./};
int main()
{
    int i, x, j, len;
    char c, s1[200];
    scanf(%c,&c);
    if(c=='L')
        x=1;
    else
        x=-1;
        scanf(%s,s1);
    len=strlen(s1);
    for(i=0;i

B題：Worms 
水題。。
代碼如下：
 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 

using namespace std;
#define LL __int64
int dp[1100000];
int main()
{
    int n, m, i, j, sum=0, x;
    scanf(%d,&n);
    for(i=0;i

C題：Captain Marmot 
暴力枚舉，共4*4*4*4種情況，對每一種情況分別判斷是否是正方形。我居然一直都以為是矩形。。
判斷方法：將4條邊與兩條對角線分別計算出來。然後排序，4個小的肯定是邊，2個大的是對角線，然後判斷邊是否都相等，對角線是否都相等，對角線是否是邊的sqrt(2)倍（這裡最好是用平方來判斷是否是2倍）。然後找出移動次數最少的輸出即可。
代碼如下：
 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 

using namespace std;
#define LL __int64
const int mod=1e9+7;
struct node
{
    LL x, y;
}t1[5], t2[5], fei[5];
node solve(node x, node y, int z)
{
    node t;
    t=x;
    int i;
    for(i=0;i

D題：Flowers 
DP，還是水題。。可以這樣考慮：
第n個只有兩種情況，若第n個是R，那麼情況數為dp[n-1]種。若第n個是W，由於W只能連續k個，所以說，第n-k+1至第n個必須都是W，那麼此時情況數為dp[n-k]種。所以狀態轉移方程為：
dp[n]=dp[n-1]+dp[n-k]。
然後用一個數組保存前綴和即可。
代碼如下：
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 

using namespace std;
#define LL __int64
const int mod=1e9+7;
LL dp[110000], sum[110000];
int main()
{
    int i, j, n, k, a, b;
    LL x=0;
    sum[0]=0;
    dp[0]=0;
    scanf(%d%d,&n,&k);
    for(i=1;i<=k-1;i++)
        dp[i]=1;
    dp[k]=2;
    for(i=k+1;i<=100000;i++)
    {
        dp[i]=dp[i-k]+dp[i-1];
        dp[i]%=mod;
    }
    for(i=1;i<=100000;i++)
    {
        sum[i]=(sum[i-1]+dp[i])%mod;
    }
    while(n--)
    {
        scanf(%d%d,&a,&b);
        printf(%I64d
,(sum[b]+mod-sum[a-1])%mod);
    }
    return 0;
}
自己能做出來的只有這麼些。。sad。。