B. Yet Another Crosses Problem
https://codeforces.com/contest/1194/problem/B
题意：给q个测试样例，每个样例给一个由黑白色格子组成的图，如果某一个格子所在的行和列全被涂黑，则构成一个十字架，求构成一个十字架最少需要把多少白色格子涂黑（*表示黑色，.表示白色）；
题解：分别用两个数组记录每行每列的 白色格子数，循环找出行 h[i] 和 列 l[j] 中白色格子和最少的，如果s[i][j]== ' . ' 还要减一。（第一遍做的时候我是是单独找的行和列中黑色格子的最大值再求，全是白色格子的情况判断就会出错。后来一直超时，是因为把string s[50010]定义在循环里了）
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 typedef long long ll; 8 int h[50010],l[50010]; 9 int main(){ 10 string s[50010]; 11 int q; 12 cin>>q; 13 while(q--){ 14 memset(h,0,sizeof(h)); 15 memset(l,0,sizeof(l)); 16 int n,m,minn=1000000; 17 cin>>n>>m; 18 for(int i=0;i<n;i++){ 19 cin>>s[i]; 20 for(int j=0;j<m;j++){ 21 if(s[i][j]=='.'){ 22 h[i]++; 23 } 24 } 25 } 26 for(int i=0;i<m;i++){ 27 for(int j=0;j<n;j++){ 28 if(s[j][i]=='.'){ 29 l[i]++; 30 } 31 } 32 } 33 int flag=0; 34 for(int i=0;i<n;i++){ 35 for(int j=0;j<m;j++){ 36 if(s[i][j]=='.'){ 37 flag=-1; 38 }else{ 39 flag=0; 40 } 41 minn=min(h[i]+l[j]+flag,minn); 42 } 43 } 44 cout<<minn<<endl; 45 } 46 return 0; 47 }
C. From S To T
https://codeforces.com/contest/1194/problem/C
题意：给字符串s,t,p,你可以从p中拿出任意字符插到字符串s的任意位置，判断能否使字符串s变成字符串t;
题解：判断字符串s是否使字符串t的子序列，判断p中的字符能否使字符串s变成字符串t
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstring> #include<cmath> #include<algorithm> using namespace std; bool check(string s,string t){ int p=0; for(int i=0;i<t.length();i++){ for(int j=p;j<s.length();j++){ if(t[i]==s[j]){ p=j+1; break; }else{ break; } } } if(p==s.length()){ return 1; }else{ return 0; } } int main(){ int q,a[27]; cin>>q; while(q--){ memset(a,0,sizeof(a)); int k=0; string s,t,p; cin>>s>>t>>p; int flag1=check(s,t); if(!flag1){ cout<<"NO"<<endl; }else{ for(int i=0;i<p.length();i++){ a[p[i]-'a']++; } for(int i=0;i<s.length();i++){ a[s[i]-'a']++; } for(int i=0;i<t.length();i++){ a[t[i]-'a']--; } int flag2=1; for(int i=0;i<26;i++){ if(a[i]<0){ flag2=0; break; } } if(flag2){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } } return 0; }
B. Buying a TV Set
https://codeforces.com/contest/1041/problem/B
题意：有一商场有多种电视机，它们的宽不超过a，高不超过b。Monocarp 想买一台电视机，但是要求宽高比满足x/y；给a,b,x,y判断有多少，求有多少电视机满足；
题解：找到x/y的最简比x0/y0，找a/x0和b/y0中最小的那个
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> using namespace std; typedef long long ll; ll gcd(ll x,ll y){ return y?gcd(y,x%y):x; } int main(){ ll a,b,x,y; cin>>a>>b>>x>>y; ll temp=gcd(x,y); x=x/temp,y=y/temp; cout<<min(a/x,b/y)<<endl; return 0; }