南華大学19級軟卓選抜試合問題解【コード逐句分析】
8472 ワード
まず去年の公式問題解をここに置いて、皆さんは19軟卓選抜公式問題解を見て、私の問題解の中で、私はすべての問題のコードを力の及ぶ限りの逐句分析を行います.
(4.21晩に修正があって、c題の問題解を更新しました)軟卓選抜A涛兄は精神軟卓選抜Aを補充して、この問題はアルゴリズムを試験していないで、1つの試験の基礎の模擬問題で、しかし問題の意味は確かに少し回ります.この問題を書くにはやはりしっかりしたc++基本功が必要だ.
ソフト卓選抜B接尾辞ゼロカウントソフト卓選抜Bこれは数学の問題で、多くの学生がこの数を計算してからいくつかの接尾辞ゼロを見ているかもしれませんが、注意しなければならないのは、longlongデータ型の限界は10の18回で、この数を完全に計算すればこの値を超えるに違いありません.だから私たちは別の方法でこの問題を解決する必要があります.もちろん、直接点数の一部を取ることができます.本当の試合はこのように一部の点数の構想を持つことができます:まず、0が現れるのは間違いなく乗算して10が現れて、乗算して10の倍数が現れてやっと0があることができて、例えば45は20に等しくて、実際には225=210は20に等しくて、それでは私達は更に10を見て、25だけが10に等しくて、103=20は253と見なすことができますでは、問題はあなたのデータが何個の2と何個の5に分解できるかを見ることに転化しました.例えば、10、2、8、5、全部で5個の2、2個の5、2個の2*5を集めることができます.その答えは2です.
软卓选抜C塔子哥算确率软卓选抜Cアルゴリズム问题、数学问题:ハッシュアルゴリズム、离散数学昨年最も难しい问题で、しかも去年先辈が书いていなかった问题です...笔者は今までやっと书きました...笔者の能力が限られているため、この问题は确かに难しいです.そのため、もし学生が本当にこの問題を知りたいなら、筆者のQQ(15366775802)をプライベートで話してください.筆者は自分で説明します.
塔子兄は言った:これは1本の原題が離散数学P 250の授業後の練習問題12.1から改編されたことを発見するのは難しくない:これは古典の概型で、分母は確定して、主に分子を計算して、つまり要求に合致する方案数である.20点の解法を持つ:三重循環、暴力統計のすべての合法案.複雑度O(n^3)は40点の解法を持つ:最適化:三重サイクル、最内層サイクルは外の二重サイクルの値によって決定し、ステップをまたいでm、複雑度O(frac{n^3}{m})は70点の解法を持つ:同余類の応用.まず本の問題の解法を徹底的に理解します.https://www.zybang.com/question/47028159d760daa405307dd3158dd42e.htmlこれにより,我々の三重サイクルの上界はnではなくmである.簡単なカウント原理に基づいて、毎回3つの同余類の中の数字の個数を統計して、組み合わせ数を求めます.内層はmapメモリi,j,kを用いたが、毎回3つの要素しか記憶していないため、この部分の複雑度は定数であり、無視できる.内層の組み合わせ数の計算は、計算回数が3に等しく、定数であり、無視されていることが明らかになった.だから総複雑度:O(m^3)が100点を取る解法:同余関係恒等式による.(i,j,kはそれぞれ3層サイクルのサイクル変数)最内層サイクルのkは、外層で定めるi,j O(1)の算出に基づいて最内層サイクルを最適化することができる.複雑度をO(m^2)に下げると,この問題を完全に通過できる.
公式コード
筆者のコード
ソフト卓選抜D小y学数学ソフト卓選抜Dは依然として思考問題であり、思いつくと難しくないが、思いつくのは難しい.君の基本も试してみよう
軟卓選抜E小y階段軟卓選抜E本題はアルゴリズム問題であり、動的計画を試験している.動的計画アルゴリズムを学んだことがない学生であれば、この問題を書くことはできない.この問題の法則を導き出さない限り、法則を探す問題になる.しかし、ダイナミックな計画が熟練している学生にとって、この問題は実は簡単です.紙面が限られているため,ここでは動的計画アルゴリズムとは何かを紹介しない.興味があればcsdnで検索して勉強することができます
ソフト卓選抜Fジェリーの2020ソフト卓選抜F非アルゴリズム問題、基礎問題は、文字列の処理と使用を考察している.考察したのはコードの基本功である.
作者:Avalon・Demerzel、このブログがあなたに役に立つことを望んで、疑問や間違いを発見したら、下のコメントを歓迎します.
(4.21晩に修正があって、c題の問題解を更新しました)軟卓選抜A涛兄は精神軟卓選抜Aを補充して、この問題はアルゴリズムを試験していないで、1つの試験の基礎の模擬問題で、しかし問題の意味は確かに少し回ります.この問題を書くにはやはりしっかりしたc++基本功が必要だ.
#include
#define ll long long
using namespace std;
int main()
{
ll t = 0;// ， 10% longlong ， longlong
cin >> t;//t
while (t--)
{
ll a, b, c, d,ans=0;
cin >> a >> b >> c >> d;//
if (a <= b)//
{
cout << b << endl;//
continue;//
}
else
{
if (c <= d)//
{
cout << "-1" << endl;// -1
continue;
}
else//
{
ans = b;//
a -= b;//
ll k = c - d;//k ，
if (a % k == 0)//
{
ans += c * (a / k);//
}
else// ， ， ， （a+k+1）
{
ans += c * ((a / k) + 1);//
}
cout << ans << endl;//
}
}
}
return 0;
}
ソフト卓選抜B接尾辞ゼロカウントソフト卓選抜Bこれは数学の問題で、多くの学生がこの数を計算してからいくつかの接尾辞ゼロを見ているかもしれませんが、注意しなければならないのは、longlongデータ型の限界は10の18回で、この数を完全に計算すればこの値を超えるに違いありません.だから私たちは別の方法でこの問題を解決する必要があります.もちろん、直接点数の一部を取ることができます.本当の試合はこのように一部の点数の構想を持つことができます:まず、0が現れるのは間違いなく乗算して10が現れて、乗算して10の倍数が現れてやっと0があることができて、例えば45は20に等しくて、実際には225=210は20に等しくて、それでは私達は更に10を見て、25だけが10に等しくて、103=20は253と見なすことができますでは、問題はあなたのデータが何個の2と何個の5に分解できるかを見ることに転化しました.例えば、10、2、8、5、全部で5個の2、2個の5、2個の2*5を集めることができます.その答えは2です.
#include
#include
#define ll long long
using namespace std;
ll x, y;// 2 5
ll a[100000];//
void fun(ll t)// t 2 ，
{
if (t % 2 == 0)
{
x++;
fun(t / 2);
}
else
return;
}
void fun2(ll t)// t 2 ，
{
if (t % 5 == 0)
{
y++;
fun2(t / 5);
}
else
return;
}
int main()
{
ll n;
cin >> n;
for (ll i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] % 2 == 0)
{
fun(a[i]);// 2， x ，
}
if (a[i] % 5 == 0)
{
fun2(a[i]);// 5
}
}
cout << min(x, y);// x，y
return 0;
}
软卓选抜C塔子哥算确率软卓选抜Cアルゴリズム问题、数学问题:ハッシュアルゴリズム、离散数学昨年最も难しい问题で、しかも去年先辈が书いていなかった问题です...笔者は今までやっと书きました...笔者の能力が限られているため、この问题は确かに难しいです.そのため、もし学生が本当にこの問題を知りたいなら、筆者のQQ(15366775802)をプライベートで話してください.筆者は自分で説明します.
塔子兄は言った:これは1本の原題が離散数学P 250の授業後の練習問題12.1から改編されたことを発見するのは難しくない:これは古典の概型で、分母は確定して、主に分子を計算して、つまり要求に合致する方案数である.20点の解法を持つ:三重循環、暴力統計のすべての合法案.複雑度O(n^3)は40点の解法を持つ:最適化:三重サイクル、最内層サイクルは外の二重サイクルの値によって決定し、ステップをまたいでm、複雑度O(frac{n^3}{m})は70点の解法を持つ:同余類の応用.まず本の問題の解法を徹底的に理解します.https://www.zybang.com/question/47028159d760daa405307dd3158dd42e.htmlこれにより,我々の三重サイクルの上界はnではなくmである.簡単なカウント原理に基づいて、毎回3つの同余類の中の数字の個数を統計して、組み合わせ数を求めます.内層はmapメモリi,j,kを用いたが、毎回3つの要素しか記憶していないため、この部分の複雑度は定数であり、無視できる.内層の組み合わせ数の計算は、計算回数が3に等しく、定数であり、無視されていることが明らかになった.だから総複雑度:O(m^3)が100点を取る解法:同余関係恒等式による.(i,j,kはそれぞれ3層サイクルのサイクル変数)最内層サイクルのkは、外層で定めるi,j O(1)の算出に基づいて最内層サイクルを最適化することができる.複雑度をO(m^2)に下げると,この問題を完全に通過できる.
公式コード
#include//
using namespace std;
const int maxn = 1e5 + 5;
#define ll long long
ll C(ll a , ll b)
{
if (a < b) return 0;
if (b == 0 || b == a) return 1;
if (b > a - b) b = a - b;
ll up = 1 , down = 1;
for (int i = 0 ; i < b ; i++){
up = up * (a - i);
down = down * (b - i);
}
return up / down;
}
ll R[maxn];
map book;
int main()
{
ll n , m ; cin >> n >> m;
for (int i = 1 ; i <= n ; i++)
R[i%m]++;
ll cnt = 0 , res = 1;
for (int i = 0 ; i < m ; i++){
for (int j = i ; j < m ; j++){
ll k = (m - i - j + 3 * m)%m;
if (k < j) continue;
if ((i + j + k)%m == 0){
book.clear();
book[i]++ , book[j]++ , book[k]++;
res = 1;
for (auto g : book) {
res *= C(R[g.first] , g.second);
}
cnt += res;
}
}
}
ll g = __gcd(cnt , C(n , 3));
cout << cnt / g << "/" << C(n , 3) / g << endl;
return 0;
}
筆者のコード
#include
#define ll long long
using namespace std;
ll gcd(ll a, ll b)//
{
return b == 0 ? a : gcd(b,a%b);
}
ll hx[2050];//
ll n, k;
ll ans;
ll res(ll x, ll y, ll z)//（x+y+z）%k==0
{
if (x == y && y == z)
{
return hx[x] * (hx[y] - 1) * (hx[z] - 2)/6; //
}
else if (x == y)
{
return hx[x] * (hx[y] - 1) * hx[z] / 2;//
}
else if (z == y)
{
return hx[x] * (hx[y] - 1) * hx[z] / 2;//
}
else
return (hx[x] * hx[y] * hx[z]);
}
int main()
{
cin >> n >> k;
for (ll i = 1; i <= n; i++)
{
hx[i % k]++;//
}
for (ll i = 0; i < k; i++)//
{
for (ll j = i; j < k; j++)
{
ll p = (k * 2 - i - j) % k;//(x+y+z)%k 0
if(p>=j)//i,j,p
{
ans += res(i,j,p);
}
}
}
ll ans2 = (n) * (n - 1) * (n - 2) / 6;// C（n 3）
ll j = gcd(ans, ans2);
ans = ans/j;
ans2 = ans2/j ;
cout << ans << '/' << ans2 << endl;
return 0;
}
ソフト卓選抜D小y学数学ソフト卓選抜Dは依然として思考問題であり、思いつくと難しくないが、思いつくのは難しい.君の基本も试してみよう
#include
#define ll long long
using namespace std;
int main()
{
ll n;
cin >> n;
if (n<10)// 10 ， ， 10
{
cout << 10+n;
return 0;
}
else
{
/* ， 9 1 ， 8=2*2*2， 2 8*/
int x9 = 0;
while (n % 9 == 0) { x9++; n /= 9; }
int x8 = 0;
while (n % 8 == 0) { x8++; n /= 8; }
int x7 = 0;
while (n % 7 == 0) { x7++; n /= 7; }
int x6 = 0;
while (n % 6 == 0) { x6++; n /= 6; }
int x5 = 0;
while (n % 5 == 0) { x5++; n /= 5; }
int x4 = 0;
while (n % 4 == 0) { x4++; n /= 4; }
int x3 = 0;
while (n % 3 == 0) { x3++; n /= 3; }
int x2 = 0;
while (n % 2 == 0) { x2++; n /= 2; }
if (n != 1)// 10 ， x1 x9 0， n 1
{
cout << -1;// -1，
return 0;
}
/* ， */
for (int i = 0; i < x2; i++)
{
cout << 2;
}
for (int i = 0; i < x3; i++)
{
cout << 3;
}
for (int i = 0; i < x4; i++)
{
cout << 4;
}
for (int i = 0; i < x5; i++)
{
cout << 5;
}
for (int i = 0; i < x6; i++)
{
cout << 6;
}
for (int i = 0; i < x7; i++)
{
cout << 7;
}
for (int i = 0; i < x8; i++)
{
cout << 8;
}
for (int i = 0; i < x9; i++)
{
cout << 9;
}
}
return 0;
}
軟卓選抜E小y階段軟卓選抜E本題はアルゴリズム問題であり、動的計画を試験している.動的計画アルゴリズムを学んだことがない学生であれば、この問題を書くことはできない.この問題の法則を導き出さない限り、法則を探す問題になる.しかし、ダイナミックな計画が熟練している学生にとって、この問題は実は簡単です.紙面が限られているため,ここでは動的計画アルゴリズムとは何かを紹介しない.興味があればcsdnで検索して勉強することができます
#include
#define ll long long
using namespace std;
ll q = 1e9 + 7;
int main()
{
int n, k;
ll dp[101];
dp[0] = 1;// 0 1
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
dp[i] = 0;
for (int j = 1; j <= k && i - j >= 0; j++)
{
dp[i] = ((dp[i] % q) + (dp[i - j] % q)) % q;
/* ， i i-1 i-k */
}
}
cout << dp[n];// n
return 0;
}
ソフト卓選抜Fジェリーの2020ソフト卓選抜F非アルゴリズム問題、基礎問題は、文字列の処理と使用を考察している.考察したのはコードの基本功である.
#include
#include
#define ll long long
using namespace std;
int main()
{
string a;
string b="";//
int ans = 0;//
cin >> a;//
for (int i = 0; i < a.size(); i++)// a ， ‘2’ ‘0’ ， b
{
if (a[i] == '2' || a[i] == '0')
{
b += a[i];
}
}
int t = 0;// t ’2020‘
for (int i = 0; i < b.size(); i++)
{
if (b[i] == '2' && t == 0)
{
b[i] = 'a';// a ， ？
t++;
}
if (b[i] == '0' && t == 1)
{
b[i] = 'a';
t++;
}
if (b[i] == '2' && t == 2)
{
b[i] = 'a';
t++;
}
if (b[i] == '0' && t == 3)
{
b[i] = 'a';
t = 0;
ans++;
}
}
cout << ans;//
return 0;
}
作者:Avalon・Demerzel、このブログがあなたに役に立つことを望んで、疑問や間違いを発見したら、下のコメントを歓迎します.