比賽鏈接：這里
OP
肝了兩個半小時A，沒過……
sl大佬也寫題解了
A SET
最大公約數
感謝老師的標程~
思路
任選兩數 a,b 做 2*a-b 運算，可以理解成 a + a - b ，即 a 加上兩數的差；
如果我們現在有 2 * a - b , a 即可通過 2 * ( 2 * a - b ) - a 得到 a + 2 * ( a - b )，即 a 加上兩數差的二倍；
如果我們現在有 3 * a - 2 * b , 2 * a - b 即可通過 2 * ( 3 * a - 2 * b ) - ( 2 * a - b ) 得到 a + 3 * ( a - b )，即 a 加上兩數差的三倍；
那所有可能被加入集合的元素即滿足
a
i
+
m
j
?
(
a
i
?
a
j
)
a_i+ m_j * ( a_i - a_j )
ai?+mj??(ai??aj?)
列舉顯然是不現實的，我們可以使式子更加普適，轉化成如下形式
a
m
i
n
+
m
?
g
c
d
（
a
2
?
a
1
,
a
3
?
a
2
,
.
.
.
,
a
n
?
a
n
?
1
）
a_{min}+ m * gcd（ a_{2}-a_{1},a_{3}-a_{2},...,a_{n}-a_{n-1}）
amin?+m?gcd（a2??a1?,a3??a2?,...,an??an?1?）
現在只需算出 gcd 并用 k 與 amin 的差對其取模即可，
看到標程之前的碎碎念：已知是需要去重，因為選兩個相同的數，產生的還是那個數，好像還和等引數列有關，
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
ll gcd(ll a,ll b)
{
while(a&&b)
{
if(a>b)a%=b;
else b%=a;
}
return a+b;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll n,k,a[N]={0},i,j;
scanf("%lld%lld",&n,&k);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
sort(a+1,a+1+n);
ll g=0;
for(i=2;i<=n;i++)
{
g=gcd(g,a[i]-a[i-1]);
}
if((a[1]-k)%g==0)printf("YES\n");
else printf("NO\n");
}
return 0;
}
B 密碼解鎖
快速冪取模+找規律
思路
我是通過打表發現，對于每個基 a ，在 k 增長時，結果有一定的周期性，
但是具體的回圈節和回圈起點我沒發現規律，便直接讓代碼自己去找，
先存下 k 取較小值（1,2,3…）時的的結果，每算出一個新值，便與前面的所有值比對，如果有相同的值，便可以找到回圈節和回圈起點，再計算 k 對應的值就好了，
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long qs(long long a,long long b,long long p)
{
long long ans=1%p;
while(b)
{
if(b&1)ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
int main()
{
ll a,k,i,j,li[20]={0},mbc,xhj=0;//mbc為第一次回圈結束位置，xhj為回圈節長度
cin>>a>>k;
li[1]=a;
mbc=1;
for(i=2;i<20&&!xhj;i++,mbc++)
{
li[mbc+1]=qs(li[mbc],li[mbc],1000);
for(j=1;j<=mbc;j++)
{
if(li[j]==li[mbc+1])
{
xhj=mbc+1-j;
}
}
}
if(k>mbc-xhj)
{k-=mbc-xhj;
k%=xhj;
printf("%lld",li[mbc-xhj+k]);}
else printf("%lld",li[k]);
return 0;
}
C 夕日坂
個人是用滑窗做的
思路
即先累乘，至成績大于目標值時，除掉前面的，同時計算以被除掉的數為起點的區間長，
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int a[100005],n,i,j,b,l[100005];
ll m;
cin>>n>>m;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
ll tim=1;
b=1;
for(i=1;i<=n;i++)
{
tim*=a[i];
while(tim>m)//大于目標值
{
l[b]=i-b;//更新區間長
tim/=a[b];
b++;//更新起始位置
}
}
for(i=b;i<=n;i++)//如果最后一段始終沒有超過目標值
{
l[i]=n-i+1;
}
for(i=1;i<=n;i++)
{
if(i!=1)printf(" ");
printf("%d",l[i]);
}
return 0;
}
D 小林的AC
字串處理
思路
分別計數aceptd六個字母的出現次數，統計每個字母能組成單詞份數的最小值即可（份數即出現次數 / 在單個單詞中的個數），
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
char g[50005];
while(cin>>g)
{
int i,a=0,c=0,e=0,p=0,t=0,d=0;
for(i=0;g[i];i++)
{
if(g[i]=='a')a++;
else if(g[i]=='c')c++;
else if(g[i]=='e')e++;
else if(g[i]=='p')p++;
else if(g[i]=='t')t++;
else if(g[i]=='d')d++;
}
int ans=min(e/2,c/2);
ans=min(ans,a);
ans=min(ans,p);
ans=min(ans,t);
ans=min(ans,d);
printf("%d\n",ans);
}
return 0;
}
E 小林刷題
貪心
思路
這道題特別像這個，
我們可以把排序問題拆分成從輸入順序開始的足夠多次對換，只要我們找到能更趨近與所求結果的對換條件，我們便可以依照此條件直接排序，
假設現在有兩道題，i 與 i + 1，我們要找到一種使對換后做兩題時耗費的精力值更小的條件，
對換前，消耗精力值之和為
(
b
1
+
b
2
+
.
.
.
+
b
i
?
1
)
?
a
i
+
(
b
1
+
b
2
+
.
.
.
+
b
i
?
1
)
?
a
i
+
1
+
b
i
?
a
i
+
1
(b_1+b_2+...+b_{i-1})*a_i+(b_1+b_2+...+b_{i-1})*a_{i+1}+b_i*a_{i+1}
(b1?+b2?+...+bi?1?)?ai?+(b1?+b2?+...+bi?1?)?ai+1?+bi??ai+1?
對換后，消耗精力值之和為
(
b
1
+
b
2
+
.
.
.
+
b
i
?
1
)
?
a
i
+
b
i
+
1
?
a
i
+
(
b
1
+
b
2
+
.
.
.
+
b
i
?
1
)
?
a
i
+
1
(b_1+b_2+...+b_{i-1})*a_i+b_{i+1}*a_i+(b_1+b_2+...+b_{i-1})*a_{i+1}
(b1?+b2?+...+bi?1?)?ai?+bi+1??ai?+(b1?+b2?+...+bi?1?)?ai+1?
減掉相同部分后，若滿足對換后小于對換前，則有
b
i
+
1
?
a
i
<
b
i
?
a
i
+
1
b_{i+1}*a_i<b_i*a_{i+1}
bi+1??ai?<bi??ai+1?
這道題的條件便是 bi+1 / ai+1 < bi / ai
通過結構體+cmp實作，
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pro
{
int a,b;
}p[500005];
bool cmp(pro x,pro y)
{
return (double)x.b/x.a<(double)y.b/y.a;
}
int main()
{
int n,i;
cin>>n;
for(i=1;i<=n;i++)scanf("%d%d",&p[i].a,&p[i].b);
sort(p+1,p+n+1,cmp);
ll bs=0,ans=0;
for(i=1;i<=n;i++)
{
ans+=bs*p[i].a;
bs+=p[i].b;
}
printf("%lld",ans);
return 0;
}
F 小林移石子
中位數
思路
即找到一點，距離所有點的距離之和最短，
這個點便是所有點坐標的中位數，
和 貨倉選址 基本相同
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,i,a[100005];
cin>>n;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
ll ans=0;
for(i=1;i<=n;i++)
{
ans+=abs(a[i]-a[n+1>>1]);
}
printf("%lld",ans);
return 0;
}
G 語汐玩游戲
思路
在游戲規則限制內，從順時針或逆時針方向看，三個牌的順序是無法被改變的，
如樣例來說，從順時針方向讀，三個牌的順序永遠是 ABCABCA…，如果目標順序相同，則可解，如目標順序不相同，如 ACBABCA… ，則不可解，
接收之后比對順序即可，
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int a[6]={0},b[6]={0},ac=0,bc=0,f=-1,i,j;
char s[5];
cin>>s;
for(i=0;i<=1;i++)
{
if(s[i]=='A')a[ac++]=1;
else if(s[i]=='B')a[ac++]=2;
else if(s[i]=='C')a[ac++]=3;
}
cin>>s;
for(i=1;i>=0;i--)
{
if(s[i]=='A')a[ac++]=1;
else if(s[i]=='B')a[ac++]=2;
else if(s[i]=='C')a[ac++]=3;
}
cin>>s;
for(i=0;i<=1;i++)
{
if(s[i]=='A')b[bc++]=1;
else if(s[i]=='B')b[bc++]=2;
else if(s[i]=='C')b[bc++]=3;
}
cin>>s;
for(i=1;i>=0;i--)
{
if(s[i]=='A')b[bc++]=1;
else if(s[i]=='B')b[bc++]=2;
else if(s[i]=='C')b[bc++]=3;
}
for(i=3;i<=5;i++)b[i]=b[i-3];//延長目標串
for(i=0;i<3;i++)
{
if(b[i]==a[0])//比對
{
for(j=1;j<=2;j++)
{
if(b[i+j]!=a[j])f=0;
}
if(f==-1)f=1;
}
}
if(f==1)printf("YES");
else printf("NO");
return 0;
}
H 字串之謎
DP
思路
對于每一個 b ，能和前面的每一個 a 組成一個 ab 串；
對于每一個 c ，能和前面的每一個 ab 串組成一個 abc 串，
更新記錄目前 a，ab，abc 的個數即可
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
char a[1000006];
ll i,ans=0,on=0,tw=0,tr=0;
cin>>a;
for(i=0;a[i];i++)
{
if(a[i]=='a')on++;
else if(a[i]=='b')tw+=on;
else if(a[i]=='c')tr+=tw;
}
printf("%lld",tr);
return 0;
}
I 小林取數
貪心
思路
求最大和，即可看成求所有的和后，如果不滿足條件，就減去最小的、能使總和滿足條件的數（非整十數），
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,a[102],i,mark=0,sum=0;
cin>>n;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]%10!=0)//標記非整十數
{
if(!mark)mark=a[i];
else mark=min(mark,a[i]);
}
sum+=a[i];//累加
}
if(sum%10!=0)printf("%d",sum);
else
{
if(mark)printf("%d",sum-mark);
else printf("0");
}
return 0;
}
ED
特別感謝老師的proA標程！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257188.html
標籤：其他
上一篇：(2021-02-04)并發編程簡介-并發編程(1)
下一篇：搜索與圖論之FloodFill