2011百校連動「菜鳥杯」プログラム設計公開試合(現更新5道)
本当の意味での菜鳥として、Aは4題落ちました...
試合は多くの問題を漏らして、最大のはコード制御能力が強くなくて、多くの簡単な問題が短い時間で叩くことができなくて、説明はやはり打つのが少ないです.後でできるだけ他の人のコードを見ないで、自分の思考を通じて問題を作るように努力して、このように同類の問題に出会ってやっと迅速にAが落ちることができます.
以下は私が作った5つの問題の簡単な分析です.
その中の1002、1005、1008はすべて本当の意味での水題です.
1002:
5文字ごとに変換すると、アルファベットが0で、数字が1で、この5つの数字に対応する10進数が得られ、26の英字に対応する答えになります.
コードは次のとおりです.
1005:
KFC行列問題、簡単な数学問題.問題をよく読めばすぐにAを落とすことができる.
コードは次のとおりです.
2文字列を比較して、メインストリングに重ならないサブストリングがいくつ含まれているかを見てみると、KMPだと思っていたのですが、多くの人がすばやく水を流していることに気づき、純暴力だと思っていました..KMPは一時半で理解できるものではない.そして果敢に暴力を振るい、果敢にAを落とす..
コードは次のとおりです.
1001:
式を,(y−x)(y+x)=nに分解し,y−x=a,y+x=bとし,列挙により結果を導く.でもTLEです.その後、数学部の学生から少し考えを聞いたところ、平均不等式によって列挙の個数を大幅に減らすことができ、numに平方を開くことで、中間から因子を下に探すことができ、最初に見つけたのはxの最小値(x=(a-b)/2)に違いない.a-bの値が小さいほどabが近いと説明できる.だから、numを平方に開いてtempを得て、tempから下に列挙して、見つけた最初のa、bが答えです.ただし、xは正の整数であるため、aとbは等しくないことに注意してください.等しいx=0であることに注意すればよい.
コードは次のとおりです.
この問題は確かに難しい法則問題ですが、matrix 67大神ブログにこの数列の紹介があることに気づきました.このブログを見ればできるはずです.実は簡単なシミュレーションです.
つまり、前の数列の1,2,3の数を判断することであり、例えば1221であれば、左から右へ遍歴して、1つ1があることを発見したので、「11」であり、それから2つ2があるので、「22」を加えて「1122」になり、それから1つ1になり、「11」を加えて「112121」になる.実は数列が左から右に繰り返される数を判断する数です.
記事リンク:http://www.matrix67.com/blog/archives/3870/comment-page-1
コードは次のとおりです.
試合は多くの問題を漏らして、最大のはコード制御能力が強くなくて、多くの簡単な問題が短い時間で叩くことができなくて、説明はやはり打つのが少ないです.後でできるだけ他の人のコードを見ないで、自分の思考を通じて問題を作るように努力して、このように同類の問題に出会ってやっと迅速にAが落ちることができます.
以下は私が作った5つの問題の簡単な分析です.
その中の1002、1005、1008はすべて本当の意味での水題です.
1002:
5文字ごとに変換すると、アルファベットが0で、数字が1で、この5つの数字に対応する10進数が得られ、26の英字に対応する答えになります.
コードは次のとおりです.
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define max(a, b) a > b ? a : b
#define min (a, b) a < b ? a : b
#pragma comment(linker, "/STACK:102400000,102400000")
char ans[26] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int main()
{
int len;
char str[10010];
int sum;
while(scanf("%d", &len) != EOF)
{
scanf("%s", str);
for(int i = 0; i < len; i += 5)
{
sum = 0;
for(int j = i; j < i + 5; ++j)
{
if(str[j] >= '0' && str[j] <= '9')
sum += pow(2.0, 4 - j % 5);
}
printf("%c", ans[sum]);
}
printf("
");
}
return 0;
}1005:
KFC行列問題、簡単な数学問題.問題をよく読めばすぐにAを落とすことができる.
コードは次のとおりです.
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
int b, d, f, p;
char que[10010];
int sum(char a)
{
if(a == 'A')
return (b + d + f);
else if(a == 'B')
return (2 * b + 2 * d + p);
else
return (3 * b + 3 * d + 2 * p);
}
int main()
{
int n;
int ans, len, mincost;
while(scanf("%d%d%d%d%d", &n, &b, &d, &f, &p) != EOF)
{
mincost = 9999999;
for(int k = 0; k < n; ++k)
{
scanf("%s", que);
len = strlen(que);
ans = 0;
for(int i = 0; i < len; ++i)
ans += sum(que[i]);
if(mincost > ans)
mincost = ans;
}
printf("%d
", mincost);
}
return 0;
}2文字列を比較して、メインストリングに重ならないサブストリングがいくつ含まれているかを見てみると、KMPだと思っていたのですが、多くの人がすばやく水を流していることに気づき、純暴力だと思っていました..KMPは一時半で理解できるものではない.そして果敢に暴力を振るい、果敢にAを落とす..
コードは次のとおりです.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
char s[1000050], p[10];
int main()
{
int ncase;
int lens, lenp;
int i, j, k, sign;
int sum;
scanf("%d", &ncase);
while(ncase--)
{
scanf("%s%s", s, p);
lens = strlen(s);
lenp = strlen(p);
sum = 0;
for(i = 0; i < lens; ++i)
{
int k = i;
for(j = 0; j < lenp; ++j)
{
if(s[k] == p[j])
k++;
else
break;
}
if(j == lenp)
{
sum++;
i += lenp - 1;
}
}
printf("%d
", sum);
}
return 0;
}1001:
式を,(y−x)(y+x)=nに分解し,y−x=a,y+x=bとし,列挙により結果を導く.でもTLEです.その後、数学部の学生から少し考えを聞いたところ、平均不等式によって列挙の個数を大幅に減らすことができ、numに平方を開くことで、中間から因子を下に探すことができ、最初に見つけたのはxの最小値(x=(a-b)/2)に違いない.a-bの値が小さいほどabが近いと説明できる.だから、numを平方に開いてtempを得て、tempから下に列挙して、見つけた最初のa、bが答えです.ただし、xは正の整数であるため、aとbは等しくないことに注意してください.等しいx=0であることに注意すればよい.
コードは次のとおりです.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
int ncase;
int num, temp;
bool flag;
scanf("%d", &ncase);
while(ncase--)
{
scanf("%d", &num);
flag = false;
temp = (int)sqrt(num * 1.0);
for(int i = temp; i >= 1; --i)
{
if(num % i != 0)
continue;
else
{
if((i + num / i) % 2 == 0 && i != num / i)
{
printf("%d
", (num / i - i) / 2);
flag = true;
break;
}
}
}
if(!flag)
printf("-1
");
}
return 0;
}この問題は確かに難しい法則問題ですが、matrix 67大神ブログにこの数列の紹介があることに気づきました.このブログを見ればできるはずです.実は簡単なシミュレーションです.
つまり、前の数列の1,2,3の数を判断することであり、例えば1221であれば、左から右へ遍歴して、1つ1があることを発見したので、「11」であり、それから2つ2があるので、「22」を加えて「1122」になり、それから1つ1になり、「11」を加えて「112121」になる.実は数列が左から右に繰り返される数を判断する数です.
記事リンク:http://www.matrix67.com/blog/archives/3870/comment-page-1
コードは次のとおりです.
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
int p[32] = {0, 1, 2, 2, 4};
string s[32] = {"", "1", "11", "21", "1211"};
void fast(int n)
{
int len = s[n - 1].length();
int sum = 1;
for(int i = 0; i < len - 1; ++i)
{
if(s[n - 1][i] != s[n - 1][i + 1])
{
if(i == len - 2)
{
s[n] += (sum + '0');
s[n] += s[n - 1][i];
s[n] += '1';
s[n] += s[n - 1][i + 1];
}
else
{
s[n] += (sum + '0');
s[n] += s[n - 1][i];
sum = 1;
}
}
else
{
sum++;
if(i == len - 2)
{
s[n] += (sum + '0');
s[n] += s[n - 1][i];
break;
}
}
}
p[n] = s[n].length();
}
int main()
{
int n;
for(int i = 5; i <= 30; ++i)
fast(i);
while(scanf("%d", &n) && n)
{
printf("%d
", p[n]);
}
return 0;
}
// ~
#include<cstdio>
int main()
{
int n;
int p[30] = {1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, 102, 134, 176, 226, 302, 408, 528, 678, 904, 1182, 1540, 2012, 2606, 3410, 4462};
while(scanf("%d", &n), n)
printf("%d
", p[n - 1]);
return 0;
}