2018年10月30日普级组
前言
结果
更正
结论:
生于忧患,死于安乐
小X的加法难题
分析
简单字符串处理
代码
#include <cstdio>
#include <cstring>
#define rr register
using namespace std;
int len=1,s1,s2; char s[103];
signed main(){
while (scanf("%s",s+len)==1&&len<=18) len+=strlen(s+len);
if (len>18) return !printf("Large");
for (rr int i=1;i<len;++i){
if (s[i]>47&&s[i]<58)
s1=(s1<<3)+(s1<<1)+s[i]-48;
else s2=s1,s1=0;
}
if (s1+s2>1e8) return !printf("Large");
else return !printf("%d",s1+s2);
}
小X的密码破译
题目
分析
用一个布尔数组装起来就没了
代码
#include <cstdio>
#include <map>
#define rr register
using namespace std;
const int mod=11111111;
bool uk[mod];
long long cnt,ans,n,a,b,c;
signed main(){
scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
for (rr int i=1;i<=n;++i)
uk[((a*i*i)%mod+b*i+c)%mod]=1;
for (rr int i=0;i<mod;++i)
if (uk[i]) ans=(ans+(++cnt)*i)%mod;
printf("%lld",ans);
return 0;
}
小X的液体混合
题目
分析
作为这套题中最有技术含量的一道题
那么这道题求的是2^(液体个数-简单环个数)
求环可以用并查集维护,但是注意要高精度
代码(小题大做的压位快速幂)
#include <cstdio>
#include <cstring>
#define rr register
using namespace std;
const int mod=1000000000;
int n,m,f[1001],tans;long long a[61],ans[61];
inline signed getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (c<48||c>57) c=getchar();
while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
return ans;
}
void times(long long *ans,long long *x){
long long c[61]; memset(c,0,sizeof(c));
for (register int i=1;i<=ans[0];i++)
for (register int j=1;j<=x[0];j++){
c[i+j-1]=c[i+j-1]+ans[i]*x[j];
c[i+j]+=c[i+j-1]/mod;
c[i+j-1]%=mod;
}
c[0]=ans[0]+x[0];
while (c[0]>1&&!c[c[0]]) c[0]--;
for (register int i=1;i<=(ans[0]=c[0]);i++) ans[i]=c[i];
}
void print(long long ans){if (ans>9) print(ans/10); putchar(ans%10+48);}
signed main(){
n=iut(); tans=m=iut();
for (rr int i=1;i<=n;++i) f[i]=i;
while (m--){
rr int fa=getf(iut());
rr int fb=getf(iut());
if (getf(fa)==getf(fb)) --tans;
else f[fa<fb?fa:fb]=fa>fb?fa:fb;
}
a[++a[0]]=2; ans[++ans[0]]=1;
while (tans){
if (tans&1) times(ans,a);
times(a,a); tans>>=1;
}
for (register int i=ans[0];i>=1;i--){
if (i!=ans[0]){
long long j=mod/10;
while (j>ans[i]&&j>1) putchar('0'),j/=10;
}
print(ans[i]);
}
return 0;
}
小X的AK计划
题目
分析
那么这道题首先是需要对于距离排序的,对于时间维护一个大根堆,对于这个大根堆每次插入一个元素,若时间超过限定那么不断弹出大的元素,then这就是思路了
代码
#include <cstdio>
#include <algorithm>
#include <queue>
#define rr register
using namespace std;
typedef long long ull; int tot,ans,answ;
struct rec{ull sit,cos;}a[100001]; ull m,sum;
inline ull iut(){
rr ull ans=0; rr char c=getchar();
while (c<48||c>57) c=getchar();
while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
return ans;
}
signed cmp(rec x,rec y){return x.sit<y.sit;}
signed main(){
rr int n=iut(); m=iut();
for (rr int i=1;i<=n;++i){
rr ull x=iut(),y=iut();
if (x+y>m) continue;
a[++tot]=(rec){x,y};
}
sort(a+1,a+1+tot,cmp);
rr priority_queue<int>q;
for (rr int i=1;i<=tot;++i){
sum+=a[i].cos+a[i].sit-a[i-1].sit;
q.push(a[i].cos); ++answ;
while (sum>m){
sum-=q.top();//减少
q.pop(); --answ;
}
ans=ans>answ?ans:answ;//每次求最大值
}
printf("%d",ans);
return 0;
}
后续
我好菜啊