2020/10/02 rating賽

C - From S To T
題意：
大體意思就是p中的值可以移動到s中，但是s中原有的值位置不能變換，看看s和p是否能轉化成t
思路：
1.首先判斷s+p構成的string型別里面是否都含有t里面的char型別的字符
2.s+p構成的字串里面的包含在t里面的字符的數量都要大于或等于t里面的字符的的數量（可以用set和multiset）
3.判斷s是否是t的子串，但是不能用普通的判斷子串的方式，需要自己定義一個函式，主要是判斷各個字符的順序，

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<set>
#include<functional>
using namespace std;
//speed_up

//判斷s是否是t的子串
bool com(string s,string t){
    int j = 0;
    for(int i = 0; i < t.length(); i++) {
		for (j; j < s.length(); j++) {
			if (t[i] == s[j]) {
				j++;
				break;
			}else{
				break;
			}
		}

	}
	if(j == s.length()) {
		return 1;
	}else{
        return 0;
	}

}


int main()
{
  int n;
  cin>>n;
  while(n--)
  {
      int sum=0;
      string s,t,p;
      cin>>s>>t>>p;
      string s1=s+p;
      set<char> tt1;
      set<char> ss1;
      set<char> pp1;
      multiset<char>tt2;
      multiset<char>ss2;
      //傳入
      for(int i=0;i<s1.size();i++)
      {
          ss1.insert(s1[i]);
          ss2.insert(s1[i]);
      }
      for(int i=0;i<t.size();i++)
      {
          tt1.insert(t[i]);
          tt2.insert(t[i]);
      }
      for(int i=0;i<p.size();i++)
      {
          pp1.insert(p[i]);
      }
      //判斷是否都在其中
      auto it=tt1.begin();
      for(it=tt1.begin();it!=tt1.end();it++)
      {
          //存在值
          if(ss1.find(*it)!=ss1.end()&&ss2.count(*it)>=tt2.count(*it))
          {

          }
          else
          {
              break;
          }
      }
      if(it==tt1.end()){sum++;}
      //cout<<"1 //"<<sum<<endl;
      //順序
      //if(tt2.count(t[0])==1)
      //{
          //if(s[0]!=t[0]&&pp1.find(t[0])==pp1.end())
          //{
              //sum--;
              //cout<<"2 //"<<sum<<endl;
          //}
      //}
      if(com(s,t)==0){sum--;}
      if(sum>0)
      {
          cout<<"YES"<<endl;
      }
      else
      {
          cout<<"NO"<<endl;
      }
  }
}

B - Yet Another Crosses Problem
題意：
大體就是讓方格圖形之中存在一個交叉的圖形最少需要涂滿幾個空格，交叉圖形就是橫向和縱向的格子全部成為了黑色
思路：
1.求每行每列相加之后白色格子數最少的那一行和一列，是最有可能變成交叉圖形的一個
2.其中每行和每列相加時，如果那一行和那一列的交點是白色的話，兩者相加的值就要減一
3.通過vector< string >將圖存入到電腦內部

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
//speed_up

int main()
{
    int t,i,j;
    cin>>t;
    while(t--)
    {
        vector<string> v;
        int n,m;
        cin>>n>>m;
        //存入行
        for(i=0;i<n;i++)
        {
            string t;
            cin>>t;
            v.push_back(t);
        }
        int x[n]={0};//初始化0
        int y[m]={0};//初始化0
        int h=0,l=0;
        //遍歷
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(v[i][j]=='.')x[i]++;
                if(v[i][j]=='.')y[j]++;
            }
        }
        //相加
        int minsum=x[0]+y[0];
        int sum;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                sum=x[i]+y[j];
                if(v[i][j]=='.'){sum--;}//判斷點
                minsum=min(minsum,sum);
            }
        }
        cout<<minsum<<endl;
    }
}

E - Buying a TV Set
題意：
商店里有任意高度和寬度的電視，找在a,b范圍內符合比例的電視有幾個
思路：
x/y化成最簡比例
（用gcd()函式取a和b的最大公約數）回傳值用long long 型別
ll gcd(ll a,ll b)//求ab最大公約數
{
return b?gcd(b,a%b):a;
}
再取a/x,b/y的最小值

#include<bits/stdc++.h>
#define ll long long
#define speed_up ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

ll gcd(ll a,ll b)//求ab最大公約數
{
    return b?gcd(b,a%b):a;
}
int main()
{
    speed_up;
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll x=gcd(c,d);
    c=c/x;
    d=d/x;
    ll m=a/c;
    ll n=b/d;
    cout<<min(m,n)<<endl;
}