第八屆“圖靈杯”NEUQ-ACM程式設計競賽個人賽（同步賽）
c 上進的小凡
分析：
這個子陣列氣死我了，我一開始是以為跟那種子序列一樣的！！可惡！！氣死我了！！它這個必須是連續的，比如樣例中，{1，2，3}是子陣列，而{1，3}不是，我們可以利用一個陣列br[i]來記錄以ar[i]為結尾的子陣列的個數，因為子陣列是連續的那么我們只需要判斷ar[i]與ar[i - 1]的關系，然后大體是這樣一個關系
if(ar[i] >= ar[i - 1]) br[i] += br[i - 1] + 1;
else br[i] = 1;//子陣列元素為1時，也是nice的
最后把br[i]全加起來即可
AC代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ar[100050];
int n;
ll br[100050], ans;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
br[1] = 1;
ans = 1;
for(int i = 2; i <= n; ++i)
{
if(ar[i] >= ar[i - 1]) br[i] += br[i - 1] + 1;
else br[i] = 1;
ans += br[i];
}
printf("%lld\n", ans);
return 0;
}
D Seek the Joker I
D題和E題都是博弈論的模板題
分析：
比較簡單的博弈問題，找到必勝態必敗態即可
AC代碼:
#include <bits/stdc++.h>
using namespace std;
int t, n, k;
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &k);
if(n % (k + 1) == 1) cout << "ma la se mi no.1!\n";
else cout << "yo xi no forever!\n";
}
return 0;
}
E Seek the Joker II
分析：
實質還是一個取石子游戲，有兩堆石子，每次可以從任意堆中取任意個（大于0），也可以從兩堆中取相同個（大于0），誰最后拿光誰贏了
AC代碼：
#include <bits/stdc++.h>
using namespace std;
int tt, nn, x;
int a, b, t;
int n, m;
double r, c;
int main()
{
scanf("%d", &tt);
r = (sqrt(5.0) + 1) / 2;
while(tt--)
{
scanf("%d %d", &nn, &x);
n = x - 1;
m = nn - x;
a = max(n, m);
b = min(n, m);
c = double(a - b);
t = (int)(r * c);
if(t == b) printf("ma la se mi no.1!\n");
else printf("yo xi no forever!\n");
}
return 0;
}
H 數羊
分析：
n,m >= 1是不好處理，通過手算3個樣例，可以發現
if(n >= 1 && m == 1) ans = 2 * n;
if(n >= 1 && m == 2) ans = 2的n次方（快速冪取模）
快速冪模板
AC代碼：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int t;
ll n, m;
ll pow_mod(ll a, ll n, ll m)
{
ll ans = 1;
a %= m;
while(n)
{
if(n & 1)
{
ans = (ans * a) % m;
}
a = (a * a) % m;
n >>= 1;
}
return ans;
}
ll A(ll n, ll m)
{
if(n == 1 && m == 0) return 2;
else if(n == 0 && m >= 0) return 1;
else if(n >= 2 && m == 0) return n + 2;
else if(n >= 1 && m >= 1)
{
if(m == 1) return n * 2;
else return pow_mod(2, n, 998244353);
}
return 0;
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%lld %lld", &n, &m);
printf("%lld\n", A(n, m));
}
return 0;
}
I 買花
分析：
因為之后的每一天都是前一天的2倍，所以買花總數是第一天的3， 7， 15…倍，即2^n 的前綴和倍，也等于2^n - 1倍（等比數列前n相和？）
還有就是這個鬼題輸出不是YES和NO是YE5和N0；一個5一個數字0…
AC代碼：
#include <bits/stdc++.h>
using namespace std;
int t, n;
bool flag;
int main()
{
cin >> t;
while(t--)
{
scanf("%d", &t);
flag = 0;
for(int i = 2; i <= 15; ++i)
{
if(n % ((1 << i) - 1) == 0)
{
flag = 1;
printf("YE5\n");
break;
}
}
if(!flag) printf("N0\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255609.html
標籤：其他
上一篇：LintCode 介紹
下一篇：漢諾塔問題詳解