第三次双周赛
7-1 打字
-
疯狂枚举
#include<bits/stdc++.h> using namespace std; int a[15]={0}; int main() { string s; cin>>s; int len=s.length(); for(int i=0;i<len;i++) { switch(s[i]){ case'1': case'Q': case'A': case'`': case'~': case'Z':a[1]++; break; case'2': case'W': case'S': case'X':a[2]++;break; case'3': case'E': case'D': case'C':a[3]++;break; case'4': case'R': case'F': case'V': case'5': case'T': case'G': case'B':a[4]++;break; case'6': case'7': case'Y': case'H': case'N': case'U': case'J': case'M':a[5]++;break; case'8': case'I': case'K': case',':a[6]++;break; case'9': case'O': case'L': case'.':a[7]++;break; case'0': case'P': case';': case'/': case'-': case'[': case 39: case']': case'=':a[8]++;break; } } for(int i=1;i<=8;i++) cout<<a[i]<<endl; return 0; }
7-2 分香肠
-
按一根肠算，分给m个人需要切m-1刀；中间本来就是分开的地方不用切，减去。
#include <bits/stdc++.h> using namespace std; int main() { int n,m; cin >> n >> m; cout << m-__gcd(m,n); return 0; }
7-3 会议安排
-
贪心算法
找出最早开始且时间最短的会议，排序
#include<bits/stdc++.h> using namespace std; struct Meet{ int bi,ei; }; bool cmp(Meet a,Meet b) { return a.ei <b.ei ; } int main() { int m; cin>>m; while(m--) { int n,ans=1; Meet meet[100005]; cin>>n; for(int i=1;i<=n;i++) cin>>meet[i].bi>>meet[i].ei; sort(meet+1,meet+n+1,cmp); int last=meet[1].ei; for(int i=2;i<=n;i++) { if(meet[i].bi >=last) { ans++; last=meet[i].ei; } } cout<<ans<<endl; } return 0; }
7-4 神秘密码
-
永远写不会的递归题
一个”[“就代表我们要达到下一层，并且每一层一开始必定会输入这一层的字符压缩的次数
如果发现字符，那么这一层的字符就是我们发现的这些字符。
#include <iostream> using namespace std; string str() { string ans; string temp; int k; char c; while(cin >> c) { if(c=='[') { cin >> k; temp = str(); for(int i = 1;i<=k;i++) ans+=temp; } else if(c==']') { return ans; } else { ans+=c; } } return ans; } int main() { cout << str(); return 0; }
7-5 国王游戏
-
贪心；高精度乘除
-
现在队列里有两个人,假设第一个人的左手为a1,右手为b1,第二个人左右手为a2,b2,他们前面所有人左手乘积为s
如果第一个人在前面是更优解,就有max(s/b2,sa2/b2)>max(s/b1,sa1/b2)
可得s/b2<=s*a1/b2
sa1/b2<sa2/b1
a1b1<a2b2
就是按a*b升序排
#include<bits/stdc++.h>
using namespace std;
struct people{
int l;
int r;
int ans; //ans为左右手数字的乘积
}arr[1005]; //用arr存放每位大臣的信息
bool cmp(const people &p1,const people &p2){
return p1.ans<p2.ans; //让每位大臣按照每位大臣的左右手乘积从小到大排序
}
int numarr[10010],len_num2=1,ans[10010],len_ans=1,numshuzu[10010],finalans[10010];
string money[1005];
int turn(int len){ //模拟进位
for(int i=0;i<len;i++){
if(numshuzu[i]>=10){
numshuzu[i+1]+=numshuzu[i]/10;
numshuzu[i]%=10;
}
if(numshuzu[len]>0){
len++;
}
}
return len;
}
string chu(int len,int chushu){ //高精度除法
int a=0,len_finalans=0;
string ans1;
for(int i=0;i<len;i++){
a=a*10+ans[i];
if(a>=chushu){
finalans[len_finalans++]=a/chushu;
ans1+=to_string(a/chushu);
a%=chushu;
}
else if(a<chushu&&len_finalans>0){
ans1+="0";
}
}
return ans1;
}
void cheng(int num,int chushu){
memset(numshuzu,0,sizeof(numshuzu));
string a=to_string(num);
int len_num1=a.length(),len_zong=0;
for(int i=0;i<len_num1;i++){
numarr[i]=a[i]-'0';
}
for(int i=len_ans-1;i>=0;i--){
len_zong=len_ans-1-i;
for(int a=len_num1-1;a>=0;a--){
numshuzu[len_zong++]+=ans[i]*numarr[a];
}
}
len_ans=turn(len_zong);
for(int i=len_ans-1;i>=0;i--){
ans[len_ans-1-i]=numshuzu[i];
}
}
int main(){
long long num,l,r,sum=1;
ans[0]=1;
cin>>num>>l>>r;
arr[0].l=l;
arr[0].r=r;
for(int i=1;i<=num;i++){
cin>>arr[i].l>>arr[i].r;
arr[i].ans=arr[i].l*arr[i].r;
}
sort(arr+1,arr+num+1,cmp);
for(int i=1;i<=num;i++){
cheng(arr[i-1].l,arr[i].r);
}
if(chu(len_ans,arr[num].r)==""){
cout<<"1"<<endl;
}
else{
cout<<chu(len_ans,arr[num].r);
}
return 0;
}