题号 标题 已通过代码 通过率 团队的状态
A Villages: Landlines 点击查看 1673/4177 通过
B Spirit Circle Observation 点击查看 39/299 未通过
C Grab the Seat! 点击查看 88/392 未通过
D Mocha and Railgun 点击查看 1589/8517 通过
E LTCS 点击查看 43/324 未通过
F Cut 点击查看 21/154 未通过
G Lexicographical Maximum 点击查看 1834/4971 通过
H Fly 点击查看 56/405 未通过
I Chiitoitsu 点击查看 648/1134 通过
J Serval and Essay 点击查看 160/1331 未通过
K Villages: Landcircles 点击查看 1/45 未通过
文章目录
- G.Lexicographical Maximum
- A.Villages: Landlines
- D.Mocha and Railgun
- I.Chiitoitsu
G.Lexicographical Maximum
题意：
- 官方
思路：
- 官方
#include<bits/stdc++.h>
using namespace std;
int main(){
string s; cin>>s;
if(s.size()==1){
cout<<s<<"\n";
return 0;
}
int ok = 1;
for(int i = 0; i < s.size()-1; i++){
if(s[i]!='9')ok = 0;
}
if(ok==0){
cout<<string(s.size()-1,'9');
}else{
cout<<s<<"\n";
}
return 0;
}A.Villages: Landlines
题意：
- 官方
思路：
- 能源站可以没有代价无限建，所以我们假设每个地方都有一个能源站好啦
- 然后电线的话，把没有连上的能源站连上，最小的代价。
- 题目等价于将n个x±r的区间联通的最小代价。
- 记得要开longlong
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 2e5+10;
struct node{ LL l, r;}a[maxn];
bool cmp(node x, node y){
return x.l!=y.l? x.l<y.l : x.r<y.r;
}
int main(){
LL n; cin>>n;
for(LL i = 1; i <= n; i++){
LL x, r; cin>>x>>r;
// cin>>a[i].l>>a[i].r;
a[i].l = x-r;
a[i].r = x+r;
}
sort(a+1,a+n+1,cmp);
LL sum = 0, last = a[1].r;
for(LL i = 2; i <= n; i++){
if(a[i].l>last){
// cout<<i<<"\n";
sum += a[i].l-last;
}
last = max(last, a[i].r);
}
cout<<sum<<"\n";
return 0;
}D.Mocha and Railgun
题意：
- 官方
思路：
- 对于P点和线段2d而言，不难想到两种特殊情况，要么就是2d和圆心连线PO垂直，要么就是重合。
- 算一下不难发现垂直弧长是最小，重合是弧长最大。
- 然后根据弦长公式等可以推出弧长。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T; cin>>T;
while(T--){
double r; cin>>r;
double x, y, d; cin>>x>>y>>d;
// printf("%.10lf\n", 2*r*asin(d/r));
double bb = acos((sqrt(x*x+y*y)+d)/r);
double aa = acos((sqrt(x*x+y*y)-d)/r);
// cout<<bb<<" "<<aa<<"\n";
printf("%.10lf\n", r*(aa-bb));
}
return 0;
}I.Chiitoitsu
题意：
- 官方
思路： - 官方std是期望dp，但是不难想到打表做法。
- 因为初始手牌只有13张，所以肯定是0对+13张，1对+11张，2对+9张，3对+7张，4对+5张，5对+3张，6对+1张这几种情况。一共也只有7种情况罢了。而且样例给出了数据最大最难算的0+13的情况和小数据5+3供验证打表正确性。
- 所以直接dfs打表，即可得到答案。
13:927105416
11:745749140
9：707741534
7：882102328
5：781250051
3：100000041
1：31
//打表
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL pows(LL a, LL x) { if(x==0)return 1; LL t = pows(a, x>>1); if(x%2==0)return t*t%mod; return t*t%mod*a%mod; }
LL pows(LL a, LL x, LL p) { if(x==0)return 1; LL t = pows(a, x>>1, p); if(x%2==0)return t*t%p; return t*t%p*a%p; }
LL exgcd(LL a, LL b, LL &x, LL &y){ if(!b){ x = 1, y = 0; return a; }else{LL r = exgcd(b, a%b, x, y); LL t = x; x = y; y = t-a/b*y; return r; }}
void exgcd(LL a, LL b, LL &d, LL &x, LL & y, LL MOD) { if (b==0) { d = a; x = 1; y = 0; } else { exgcd(b, a % b, d, y, x, MOD); y -= x * (a / b); } }
LL inv(LL a, LL MOD) { LL d=0, x=0, y=0; exgcd(a, MOD, d, x, y, MOD); return d == 1 ? (x + MOD) % MOD : -1; }
LL sum=0;
void dfs(int d,int p,int r,LL w){//轮数,单牌,牌库,概率
if(p<=0){
sum=(sum+w*(d-1)%mod)%mod;
return ;
}
dfs(d+1,p-2,r-1,w*p%mod*3%mod*inv(r,mod)%mod);//摸到对子，单牌-2，牌库-1, 概率*=p*3/牌库(每种牌p当前牌库里肯定还有3张)
if(r>p*3) dfs(d+1,p,r-1,(w*(r-p*3)%mod*inv(r,mod)%mod)%mod);//摸到单牌，单牌不变，牌库-1，概率*=(牌库-p*3)/牌库
}
int main(){
dfs(1,3,34*4-13,1);//开局3张单牌(相同牌开局最多出现两张！所以单牌，牌库里肯定还有3张)
cout<<sum<<"\n";
return 0;
}#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL mod = 1e9+7;
int getid(string s){ //1-34
if(s[1]=='m')return s[0]-'0';
if(s[1]=='p')return s[0]-'0'+9;
if(s[1]=='s')return s[0]-'0'+18;
if(s[1]=='z')return s[0]-'0'+27;
return 0;
}
int now[50], all[50];
int main(){
IOS;
int T; cin>>T;
for(int _w = 1; _w <= T; _w++){
cout<<"Case #"<<_w<<": ";
string s; cin>>s;
memset(now,0,sizeof(now));
for(int i = 0; i < (int)s.size(); i+=2){
int id = getid(s.substr(i,2));
now[id]++;
all[id] = (all[id]+4-1)%4;
if(now[id]==2)now[id] = 0;
}
// //开局单牌数量
int cnt = 0;
for(int i = 1; i <= 34; i++){
if(now[i]!=0)cnt++;
}
if(cnt==1)cout<<"31\n";
else if(cnt==3)cout<<"100000041\n";
else if(cnt==5)cout<<"781250051\n";
else if(cnt==7)cout<<"882102328\n";
else if(cnt==9)cout<<"707741534\n";
else if(cnt==11)cout<<"745749140\n";
else if(cnt==13)cout<<"927105416\n";
}
return 0;
}