哈理工2019新生赛解题报告

没啥好写的但毕竟也是ak了

来看压行小天才的表演

A: 会长的烦心事

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int len[15];
int change(char c){
if(c=='l') return 0;
if(c=='e') return 1;
if(c=='a') return 2;
if(c=='g') return 3;
if(c=='u') return 4;
if(c=='o') return 5;
if(c=='f') return 6;
return 7;
}
int main(){
string s; while(cin>>s){
int n=s.length(); rep(i,0,7) len[i]=0;
rep(i,0,n) len[change(s[i])]++;
len[0]/=2; len[1]/=2; int mn=1e9;
rep(i,0,7) mn=min(mn,len[i]); cout<<mn<<'\n';
}
}

B: 快来秒掉我!

题目链接
嗯!第一次写php(逃

1
Do you want to play ACM?(yes\no)

C: 素数圆环

题目链接
暴搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int n,cas,ans[25],vis[25];
int p[25]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1};
void dfs(int x){
if(x>n&&p[ans[n]+1]) rep(i,1,n+1)
cout<<ans[i]<<(char)(i==n?'\n':' ');
if(x<=n) rep(i,2,n+1) if(!vis[i]&&p[i+ans[x-1]]){
vis[i]=1; ans[x]=i; dfs(x+1); vis[i]=0;
}
}
void solve(){
cout<<"Case "<<++cas<<":\n"; ans[1]=1;
if(n%2==0) dfs(2); cout<<'\n';
}
int main(){
while(cin>>n&&n) solve();
}

D: 电脑磨损程度

题目链接
委屈,它卡cout精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int solve(int n){
if(n<=4) return cout<<10<<'\n',0;
int r=n%8,c=n/8; if(!r) return cout<<c*18<<'\n',0;
if(r==1) return cout<<c*18+2<<".4"<<'\n',0;
if(r==2) return cout<<c*18+4<<".8"<<'\n',0;
if(r==3) return cout<<c*18+7<<".2"<<'\n',0;
if(r==4) return cout<<c*18+9<<".6"<<'\n',0;
return cout<<c*18+10+(r-4)*2<<'\n',0;
}
int main(){
int n; while(cin>>n&&n) solve(n);
}

E: ACMer如何拯救小学生

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
string s;
int main(){
int _; cin>>(_); getchar(); while(_--){
getline(cin,s); int n=s.length();
string t=""; t+=toupper(s[0]); rep(i,1,n){
if(s[i-1]==' '&&s[i]!=' ') t+=toupper(s[i]);
} cout<<t<<'\n';
}
}

F: 当会长和一群手贱的耗子在电梯相遇

题目链接
算因数个数

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
#define rep(i,s,e) for(ll i=s; i<e; ++i)
using namespace std;
typedef long long ll;
void solve(ll n){
ll cnt(0); rep(i,1,1e8){
if(i*i>n) break; if(n%i==0) cnt+=i*i==n?1:2;
} puts(cnt&1?"Goddess,I'm coming~~~":"Farewell~");
}
int main(){
ll n; while(cin>>n&&n) solve(n);
}

G: ACMer分奖金

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int main(){
int _; cin>>_; while(_--){
int num[10]; rep(i,0,6) num[i]=0;
int n; cin>>n; rep(i,0,n){
int a; cin>>a; num[0]+=a/100; a%=100;
num[1]+=a/50; a%=50; num[2]+=a/20; a%=20;
num[3]+=a/10; a%=10; num[4]+=a/5; a%=5; num[5]+=a;
} int sum(0); rep(i,0,6) sum+=num[i];
cout<<sum<<'\n';
}
}

H: 放轻松

题目链接

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
double a[15];
int main(){
int n; while(cin>>n){
rep(i,0,n) cin>>a[i]; sort(a,a+n);
rep(i,0,n) printf("%.2lf ",a[i]); cout<<'\n';
}
}

I: ACM协会晚会

题目链接
组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
const int mod = 1e18;
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1,y=0; return; }
else{ exgcd(b,a%b,y,x); y-=(a/b)*x; return; }
}
ll C(int s,int x){
if(s>x-s) s=x-s;
ll ans=1,tmp=1,xx,y;
rep(i,1,s+1) ans=ans*(x-i+1)%mod,tmp=tmp*i%mod;
exgcd(tmp,mod,xx,y); ans=(ans*xx%mod+mod)%mod;
return ans;
}
int solve(){
int n,m; cin>>n>>m; if(m>n) return puts("0");
return cout<<C(m,n)<<'\n',0;
}
int main(){
int _; cin>>_; while(_--) solve();
}

J: 会长爱旅游

题目链接
bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 1e5 + 5;
vector<int>vv[maxn];
int vis[maxn],ans[maxn];
void bfs(int s){
queue<int>q; q.push(s); while(!q.empty()){
int fr=q.front(); q.pop(); for(int t:vv[fr])
if(!vis[t]) vis[t]=1,ans[t]=fr,q.push(t);
}
}
int main(){
int _; cin>>_; while(_--){
int n,s; cin>>n>>s; mst(vv,0); rep(i,1,n){
int x,y; cin>>x>>y; vv[x].push_back(y); vv[y].push_back(x);
} ans[s]=-1; vis[s]=1; bfs(s);
rep(i,1,n+1) cout<<ans[i]<<(char)(i==n?'\n':' ');
}
}

压行选手是这么牛逼的