先在開頭吐槽一下這場比賽修改了n次題面甚至改了資料,題面的糟糕程度實屬第一次見,
這場比賽難的不是題目,是出題人,這場比賽可能是沒有經過嚴格的驗題,
A題
相關tag:數學
如果我們把1劃分成x份,那么每份就是1/x,
我們希望最后的k個人得到的盡可能平均,那么每個人必然是拿到[x/k]份的1/x或者[x/k]+1份的1/x,
那么每個人得到的值,與平均值x/k的差值是不可能大于1/x的,
題目要求差值不超過1/210,那么我們把1切成x=1024份,每份的值為1/1024,再平均分配打包給所有人就是了,
切割成1024份需要的次數為20+21+22+…+29=1023次,在加上打包k次,次數必定在6000次內,
(當然你切成2048份也行,仍然在6000次內)
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=30+7;
const int mod=998244353;
int k;
int ans=1023;
int main()
{
scanf("%d",&k);
printf("%d\n",ans+k);
int now=1;
for(int i=0;i<=9;i++)
{
for(int j=0;j<now;j++)
printf("1 %d\n",i);
now*=2;
}
int num=1024;
int a=num/k,b=num%k;
for(int i=1;i<=k;i++)
{
printf("2");
if(i<=b)
{
printf(" %d",a+1);
for(int i=0;i<=a;i++) printf(" 10");
printf("\n");
}
else
{
printf(" %d",a);
for(int i=0;i<a;i++) printf(" 10");
printf("\n");
}
}
}
B題
相關tag:前綴和
使用num[i]記錄第i個數字為多少,
使用sum[i]記錄前綴和,也就是前i個數字值的和,
如果某一個區間[l,r]的數字加起來為k的整數倍,
那么必定有(num[r]-num[l-1])%k=0,
也等價于num[r]%k=num[l-1]%k
我們可以依靠前綴和對k取模的結果,
cas[i]記錄前綴和對k取模為i的前綴和,第一次出現在哪里,
每次出現取模為i的前綴和時,用當前位置減去第一次出現的位置,即為該位置為右邊界可以找到的最長區間了,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=30+7;
ll ans,n,k;
ll num[100007];
ll cas[100007];
int main()
{
int t;scanf("%d",&t);
while(t--)
{
ans=-1;
for(int i=1;i<100007;i++) cas[i]=-1;
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%lld",&num[i]);
num[i]=(num[i]+num[i-1])%k;
if(cas[num[i]]==-1) cas[num[i]]=i;
else ans=max(ans,i-cas[num[i]]);
}
printf("%lld\n",ans);
}
}
C題
相關tag:數學
首先從左往右看,我們可以按照連續的不下降區間,把整個陣列劃分成各塊區間,
由于相鄰兩個區間之間,相鄰的那兩個數的值必定是下降的,
因此我們選擇滿足條件的子陣列,只能在每塊區間里找,
對于一個長度為x的區間,
長度為1的連續子陣列有x種取法,
長度為2的連續子陣列有x-1種取法,
…
長度為x的連續子陣列用1種取法,
該區間的總取法為(1+2+…+x)=x
×
\times
× (x+1)/2種,
所有區間的取法加起來即可,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=30+7;
ll ans=0,n;
ll num[100007];
ll cas=0;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&num[i]);
if(num[i]>=num[i-1]) cas++;
else
{
ans+=cas*(cas+1)/2;
cas=1;
}
}
ans+=cas*(cas+1)/2;
printf("%lld\n",ans);
}
D題
相關tag:簡單博弈
只有1張牌的時候,先手必輸,
有x=[2,k+1]張牌的時候,先手的人可以拿走x-1張牌,剩下1張,所以先手必勝,
有x=k+2張牌的時候,先手的人不管拿走[1,k]的任意張數,剩下的數量必定落在[2,k+1]的區間里,先手必輸,
當x=[k+3,2k+2]張牌的時候,同上,先手必勝
當x=2k+3張牌的時候,同上,先手必輸,
…
歸納后得到,當x=d
×
\times
×(k+1)+1時候(d為常數),先手必輸,其他情況先手必勝,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=1e5+7;
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n,k;scanf("%d%d",&n,&k);
if((n-1)%(k+1)==0) printf("ma la se mi no.1!\n");
else printf("yo xi no forever!\n");
}
}
E題
相關tag:博弈
(出題人題面的輸出和實際樣例的輸出都能不一樣的,一個是no.1!,一個是no1.!,一個題就算了,好幾個題的題面都有問題,是真的絕活)
首先我們算出在烏龜上方和下方分別有a和b張牌,
如果a>b的話,我們交換一下a,b的值,保證a<=b,
接下來,按照a的值為0,1,2,…15e5分類討論,
a=0的情況:
a=0,b=0的時候,先手負,
a=0,b>0的時候,先手可以一次拿光b,先手勝,
a=1的情況:
a=1,b=1的時候,先手a和b都拿掉1,先手勝,
a=1,b=2的時候,先手如果想贏,那么就必須要讓當前的狀態變為先手負(操作之后當前后手的人變為下次操作的先手),而之前的先手負的狀態只有a=0,b=0,我們從a=1,b=2的狀態怎么取都是得不到a=0,b=0的,因此此時先手負,
a=1,b>2的時候,我們可以把b拿掉b-2的部分,使得變成a=1,b=2的先手負(當前的后手)狀態,因此先手勝,
a=2的情況:
a=2,b>=2的所有狀況,都可以從b取走b-1個,使得變為a=2,b=1也就是a=1,b=2的情況,先手必勝,
a=3的情況:
a=3,b=3或等于4的時候,可以同時從a和b中拿掉3或者2,得到a=0,b=0或者a=1,b=2,因此先手勝,
a=3,b=5的時候,前面的先手負狀態只有a=0,b=0或者a=1,b=2,我們不論如何操作都無法得到這兩種狀態,因此先手負,
a=3,b>5的時候,先手可以從b拿走b-5個,使得剩下a=3,b=5個,因此先手勝
…
歸納后實際上會發現,當a>0的情況下,
對于某一類a=x,先手如果想贏,當b還不是很大的狀態下,只能通過同時取走a和b一部分值,得到a<x的某個先手負狀態來取勝,當前面沒有a和b差值等于當前狀態的情況下,那么此時的先手玩家只能把當前狀態移動到先手勝的狀態,因此當前的先手必敗,那么對應的必敗狀態的a和b的差值,會比前面已經出現過的大1,
最開始的時候先手負狀態只有a=0,b=0,a和b差值為0,
后續有a=1,b=2,a和b差值為1,
再后續a=3,b=5,a和b差值為2,
再后續a=4,b=7,a和b差值為3,
…
注意到這里跳過了a=2的狀態,這是因為在a<2的狀態中有一個a=1,b=2的狀態是先手負,
我們可以把b取b-2個,變為上述狀態來獲勝,
也就是說,對于我們當前a=x的狀態,如果在前面的a<x的某一個狀態中存在b=x使得先手負的,那么a=x的所有情況都是必勝,
由此綜上,用一個dis記錄下一個先手負狀態a和b的差值應該為多少,
使用cas[i]記錄對于a=i,b=cas[i]時先手負,cas[i]=-1時代表此時b不論取什么值先手必勝,
那么們可以一路從小到大去回圈a的值,
如果當前的a值,沒有在前面計算的b中出現過,代表當前a的值存在一種先手負的狀態,當b=a+dis時必敗,并且更新cas[b]=-1,
如果當前的a值已經在前面計算的b中出現過,也就是說cas[a]=-1,那么當前a的值必勝,
以上,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=3e6+7;
ll cas[maxn];
ll dis=1;
int main()
{
for(int i=1;i<maxn;i++)
{
if(cas[i]!=-1)
{
cas[i]=i+dis;
if(i+dis<maxn) cas[i+dis]=-1;
dis++;
}
}
int t;scanf("%d",&t);
while(t--)
{
ll n,x;scanf("%lld%lld",&n,&x);
ll a=x-1,b=n-x;
if(a>b) swap(a,b);
if(cas[a]==-1||cas[a]!=b) printf("yo xi no forever!\n");
else printf("ma la se mi no.1!\n");
}
}
F題
相關tag:模擬,哈希,卡時間
資料很大,一開始交了一發試一下,果然tle了,(那你為什么要交)
加了個快讀,用了unordered_map這個O(1)的哈希map就過掉了,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=30+7;
const int mod=998244353;
int read() //整數讀入掛
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
vector<string>grade[107];
int n;
struct Node
{
int grade,num,sex;
};
unordered_map<string,Node>MAP;
char temp[10007];
int main()
{
n=read();
for(int i=0;i<n;i++)
{
string name;
Node a;
scanf("%s",temp);
a.grade=read();
a.sex=read();
a.num=read();
int len=strlen(temp);
for(int i=0;i<len;i++)
name+=temp[i];
MAP[name]=a;
grade[a.grade].push_back(name);
}
for(int i=0;i<=100;i++) sort(grade[i].begin(),grade[i].end());
int k;cin>>k;
while(k--)
{
int ope;cin>>ope;
if(ope==1)
{
string name;
scanf("%s",temp);
int len=strlen(temp);
for(int i=0;i<len;i++)
name+=temp[i];
Node a=MAP[name];
printf("%d %d %d\n",a.grade,a.num,a.sex);
}
else
{
int x;cin>>x;
for(int i=0;i<grade[x].size();i++)
{
for(int j=0;j<grade[x][i].size();j++)
printf("%c",grade[x][i][j]);
printf("\n");
}
}
}
}
G題
相關tag:貪心
看注釋吧
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=1e5+7;
const int mod=998244353;
ll num[maxn];
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n;
ll k;
scanf("%d%lld",&n,&k);
ll M=0;
int tar=0;//記錄下派蒙在第幾個
for(int i=1;i<=n;i++)
{
scanf("%lld",&num[i]);
if(num[i]>M)
{
tar=i;
M=num[i];
}
num[i]+=num[i-1];//前綴和
}
ll yici=M+n-1;//代表一次回圈最少要吃掉多少個
if(k<tar-1) printf("NO\n");//前面的tar個人最少每個人要吃一個
else
{
ll rest=(k-tar+1)%(yici);//代表除了派蒙的人每人都只吃1個的情況,最后剩下的部分
ll cas=(k-tar+1)/yici;//在上述情況下總共有多少輪回圈(這里的回圈,派蒙是第一個人)
cas*=(num[n]-M);//每輪回圈我們最多還可以再多吃總的個數減去派蒙的個數
cas+=num[tar-1]-tar+1;//在開始回圈前,一開始就排在派蒙前面的tar-1個人,除了最基本的每人吃一個外,最多還能吃幾個
if(cas>=rest) printf("YES\n");//如果能多吃的部分大于剩余的部分,代表我們能有一種安排,使得某次回圈開始時,派蒙去吃東西的時候k已經為0
else printf("NO\n");
}
}
}
H題
相關tag:簡單規律,快速冪
m只有0,1,2三種狀態,稿紙上推演一下,總結規律即可,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=30+7;
const int mod=998244353;
ll qpow(ll x,ll p)
{
ll ret=1;
while(p)
{
if(p&1) ret=ret*x%mod;
x=x*x%mod;
p>>=1;
}
return ret;
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
ll n,m;scanf("%lld%lld",&n,&m);
if(m==2) printf("%lld\n",qpow(2,n));
else if(m==1)
{
if(n==0) printf("1\n");
else printf("%lld\n",n*2);
}
else
{
if(n<2) printf("%lld\n",n+1);
else printf("%lld\n",n+2);
}
}
}
I題
相關tag:數學,暴力
如果我們選擇了k天,第一天選擇了d朵,
那么總的花的數量就是d
×
\times
× (20+21+…+2k-1)
也就是說對于選擇第k天的情況來說,如果存在滿足的整數d,那么總的花數量n需要滿足n能整除 (20+21+…+2k-1)
因此我們直接處理出k=2到15這些天數的 (20+21+…+2k-1),用n一一去暴力嘗試整除即可,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=30+7;
ll cas[20];
int main()
{
cas[1]=1;
for(int i=2;i<=15;i++) cas[i]=cas[i-1]*2;
for(int i=2;i<=15;i++) cas[i]+=cas[i-1];
int t;scanf("%d",&t);
while(t--)
{
ll n;scanf("%lld",&n);
bool flag=0;
for(int i=2;i<=15;i++) if(n%cas[i]==0) flag=1;
if(flag) printf("YE5\n");
else printf("N0\n");
}
}
J題
相關tag:模擬
模擬,沒什么好說的,大一同學去學一下如何存圖,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=30+7;
const int mod=998244353;
int n,m;
int field[307][307];
bool flag[307];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b,w;scanf("%d%d%d",&a,&b,&w);
if(field[a][b]==0) field[a][b]=field[b][a]=w;
else field[a][b]=field[b][a]=min(field[a][b],w);
}
ll ans=llINF;
int k;scanf("%d",&k);
while(k--)
{
for(int i=1;i<=n;i++) flag[i]=0;
int cnt=0;
ll sum=0;
bool f=1;
int x;scanf("%d",&x);
int now=0;
while(x--)
{
int to;scanf("%d",&to);
if(field[now][to]==0) f=0;
sum+=field[now][to];
now=to;
if(flag[to]==0) {flag[to]=1;cnt++;}
}
if(field[now][0]==0||cnt!=n) f=0;
sum+=field[now][0];
if(f) ans=min(ans,sum);
}
if(ans==llINF) printf("-1\n");
else printf("%lld\n",ans);
}
K題
相關tag:模擬
注意一下字符為z或者Z的特殊情況即可,
另外出題人爬
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
vector<char>c[4];
vector<int>num[4];
int cntc=0,cntn=0;
char change(char c)
{
if(c=='Z') return 'b';
if(c=='z') return 'B';
return c+1;
}
int main()
{
string s;cin>>s;
for(int i=0;i<32;i++)
{
if(s[i]>='0'&&s[i]<='9')
{
num[cntn].push_back(s[i]-'0');
cntn=(cntn+1)%4;
}
else
{
c[cntc].push_back(s[i]);
cntc=(cntc+1)%4;
}
}
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
for(int k=0;k<num[i][j];k++)
c[i][j]=change(c[i][j]);
}
}
for(int i=0;i<4;i++)
{
for(int j=3;j>=0;j--)
printf("%c",c[j][i]);
}
printf("\n");
}
L題
相關tag:二分答案
很好的一個二分答案例題,
對于我們最后站臺之間相鄰距離的最大值L,隨著L的增大,我們需要設定的站臺數量只可能變少不可能變多,滿足二分條件,存在某一個值x,使得當L>=x時,站臺數量<=k,
可以借此寫出一個二分,
對于每對相鄰的車站,他們的距離如果為dis,我們check的距離為x,
那么這段距離之中除了左右兩側已經有的城市外,需要的站臺數量就是(dis/x+dis%x?1:0)-1,
由此算出距離x對應需要的最少站臺數量sum,用sum與題目要求k對比即可check正確性,
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=1e5+7;
ll num[maxn];
ll dis[maxn];
int n,k;
bool check(ll x)
{
ll sum=0;
for(int i=1;i<n;i++)
{
if(dis[i])
{
ll temp=dis[i]/x;
if(dis[i]%x) temp++;
sum+=temp-1;
}
}
return sum<=k;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%lld",&num[i]);
sort(num,num+n);
bool flag=1;
for(int i=1;i<n;i++)
{
dis[i]=num[i]-num[i-1];
if(dis[i]!=0) flag=0;
}
if(flag) printf("0\n");
else
{
ll l=1,r=1e12;
while(l<r)
{
ll mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%lld\n",l);
}
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/254839.html
標籤:其他
上一篇:一個強迫癥的電腦上(桌面篇)
下一篇:HTML視頻無法自動播放問題
