1、光劍
(sword.pas/c/cpp)
【題目描述】
小林和亮亮各有一把光劍,長度分别為 a 和 b,他們拿光劍進行比試。每一回合,長光劍會砍向短光劍,砍完後,短光劍完好無損,而長光劍則被截成兩段,被截去的長度恰好等于短光劍的長度。若兩把光劍長度相等,則比試結束。請問小林和亮亮将比試多少回合?
【輸入格式】
第一行一個整數 T,表示資料組數。
接下來 T 行每行兩個正整數 a,b,表示初始狀态光劍的長度。
【輸出格式】
每組資料輸出一個整數,表示能進行幾個回合的比試。
【樣例輸入】
3
1 8
3 7
6 6
【樣例輸出】
7
4
【資料規模】
對于 40%的資料,0 < a,b <= 1000, 1 <= T <= 20;
對于 100%的資料,0 < a,b <= 10^18,1 <= T <= 1000。
題解:模拟輾轉相除。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll x, y, T;
int main()
{
freopen("sword.in","r",stdin);
freopen("sword.out","w",stdout);
ios::sync_with_stdio(false);
cin>>T;
for(ll a = 1; a <= T; a++)
{
ll round = 0, now;
cin>>x>>y;
if(x < y) swap(x, y); // x 大 y 小
if(x == y)
{
cout<<0<<endl;
continue;
}
while(x % y != 0)
{
round += x/y; // x = 7 y = 3
now = x % y; // now = 1
x = y;
y = now;
}
cout<<round-1+x/y<<endl;
}
}
2、化零
(zero.pas/c/cpp)
Describe
有5個集合,每個集合N個元素,從每個集合選出一個數,共5個,問是否可以使和為0。
IN put:
第一行一個整數 N,表示集合的大小。
接下來五行每行 N個整數,表示這五個集合内的元素。
OUT put:
如果能找到符合條件的五個數,則輸出“YES”,否則輸出“NO”。
example:
in
3
1 -2 9
-1 2 1
-3 5 1
-1 7 6
-4 -1 -7
out
YES
資料範圍:
N<=20 30%
N<=200 100%
題解:
考慮 N <= 20 直接N^5暴力
對于 N > 20 考慮一種賭博式的想法
如果有合法解的話,不妨設在前兩個集合和後三個集合存在相反數
這樣我們可以預先處理出N^2 和 N^3 的方案數,再進行組合,看是否有相反數
這時候我們先排序再套個lower_bound就ok了
最差在沒有解大概跑了1.11s
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 210;
ll a[maxn], b[maxn], c[maxn], d[maxn], e[maxn], n;
ll ans1[41000], ans2[8000100], cnt1 = 0, cnt2 = 0;
inline ll read()
{
ll k=0,f=1;
char c=getchar();
while(!isdigit(c))
{
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c))
{
k=(k<<1)+(k<<3)+c-48;
c=getchar();
}
return k*f;
}
int main()
{
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= n; i++) b[i] = read();
for(int i = 1; i <= n; i++) c[i] = read();
for(int i = 1; i <= n; i++) d[i] = read();
for(int i = 1; i <= n; i++) e[i] = read();
if(n <= 25)
{
for(int v = 1; v <= n; v++)
for(int w = 1; w <= n; w++)
for(int x = n; x >= 1; x--)
for(int y = n; y >= 1; y--)
for(int z = n; z >= 1; z--)
{
if(a[v] + b[w] + c[x] + d[y] + e[z] == 0)
{
cout<<"YES"<<endl;
return 0;
}
}
cout<<"NO"<<endl;
return 0;
}
else
{
for(int v = 1; v <= n; v++)
for(int w = 1; w <= n; w++)
ans1[++cnt1] = a[v]+b[w];
for(int x = 1; x <= n; x++)
for(int y = 1; y <= n; y++)
for(int z = 1; z <= n; z++)
ans2[++cnt2] = -1*(c[x]+d[y]+e[z]);
sort(ans1+1, ans1+1+cnt1);
for(int i = 1; i <= cnt2; i++)
{
int now = lower_bound(ans1+1, ans1+1+cnt1, ans2[i])-ans1;
if(ans1[now] == ans2[i])
{
cout<<"YES"<<endl;
return 0;
}
}
cout<<"NO"<<endl;
return 0;
}
}
3、2048
(2048.pas/c/cpp)
【題目描述】
小林和亮亮最近正在重溫 2048 這款遊戲。由于他們的遊戲水準高超,覺得沒有什麼挑戰性,于是決定自己設計一款類似的遊戲。他們設計的遊戲中,數字排成了一個線性的序列,每次玩家可以将序列中任意兩個相同的數 a 合并,成為一個新的數 2*a,當合并出 2048 時遊戲即獲得勝利。設計完後,他們發現這個遊戲比原來的版本更加簡單了,于是他們就開始計算,對于一個給定的長度為 n 的序列,它共有多少子序列可以合并出 2048。請給出這個數模 998244353 後的值。
【輸入格式】
第一行有一個整數 n。
第二行 n個整數Ai,表示數列中的數。
【輸出格式】
一個整數,即為所求的答案。
【樣例輸入】
2
2048 2048
【樣例輸出】
3
【資料規模】
對于 40%的資料,n <= 20;
對于 70%的資料,n <= 500;
對于100%的資料,1 <= n <= 100000,1 <= Ai <= 2048。
題解:
組成2048必須是2的幂次方。
不是的統計到cnt,可以直接扔掉了。
設dp[i][j]表示使用前i個數使他們和為j的方案數
ans = dp[n-cnt][2048]*(1<<cnt)
code不是我的= =考試沒寫出來,現在也沒寫出來qwq
#include <cstdio>
#include <cstring>
#define MOD 998244353LL
#define F 2100
using namespace std;
typedef long long LL;
int n, x, cnt = 0;
LL a[F], num[F];
void Read(int &x)
{
x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
}
int main()
{
freopen("2048.in", "r", stdin);
freopen("2048.out", "w", stdout);
Read(n);
memset(num, 0, sizeof(num));
memset(a, 0, sizeof(a));
for (int i = 0; i <= 11; i++)
num[1<<i] = i;
for (int i = 1; i <= n; i++)
{
Read(x);
if (!num[x] && x != 1) { cnt++; continue; }
for (int j = 2048; j >= 1; j--)
if (a[j])
{
if (j + x <= 2048) a[j+x] = (a[j+x] + a[j]) % MOD;
else a[2048] = (a[2048] + a[j]) % MOD;
}
a[x]++;
}
for (int i = 1; i <= cnt; i++)
a[2048] = a[2048] * 2LL % MOD;
printf("%d\n", a[2048]);
return 0;
}
轉載于:https://www.cnblogs.com/MisakaAzusa/p/9790126.html