第一题

#include<bits/stdc++.h>
using namespace std;
bool st[200024];
double a[200024],c[200024];
int n,m;
double ans=0;
bool cmp(double x,double y){
	return x>y;
}
int main(){
    freopen("multi.in","r",stdin);
    freopen("multi.out","w",stdout);
	cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int j=1;j<=m;j++)cin>>c[j];
    for(int i=m-1;i>=1;i--)c[i] *=c[i+1];
    sort(a+1,a+1+n,cmp);
    sort(c+1,c+1+m,cmp);
    for(int i=m;i>0;i--){
        if(c[i]<0)ans+=a[n+i-m]*c[i];
        else ans+=a[i]*c[i];
    }
    printf("%.1lf",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

第二题

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;cin>>n;
    int num2=0,num5=0;
    for(int i=1;i<=n;i++){
        long long x;
        cin>>x;
        while(x%2==0){x/=2;num2++;}
        while(x%5==0){x/=5;num5++;}
    }
    cout<<min(num2,num5)<<endl;
    return 0;
}

第三题

/*
#include <bits/stdc++.h>               
using namespace std;
string s[200034];                        // 地图网格，每行一个字符串
int n, m;                                // 网格行数 n、列数 m
bool vis[50][50];                        // 访问标记（DFS 用），假设 n,m ≤ 50
int dx[4] = { -1, 1, 0, 0 };             // 四联通方向：上、下、右、左 的 x 增量
int dy[4] = { 0, 0, 1, -1 };             // 四联通方向：上、下、右、左 的 y 增量
vector<pair<int,int>> v;                 // 记录与起点的相对坐标集合
bool check(int x, int y) {// 检查 (x,y) 是否在边界内，且该格不是 'O'（黑洞）
    if (x >= 0 && x < n && y >= 0 && y < m && s[x][y] != 'O') return 1;
    return 0;
}
// 从 (x,y) 出发的 DFS，sx,sy 为起始点坐标，用于记录相对位移
void dfs(int x, int y, int sx, int sy) { // x,y 是当前位置，sx,sy 是起始点
    v.push_back({ x - sx, y - sy });     // 记录当前点相对起点的位移，形成形状模板
    vis[x][y] = 1;                       // 标记已访问
    for (int i = 0; i < 4; i++) {        // 枚举四个方向
        int nx = x + dx[i];              // 邻接格子的 x
        int ny = y + dy[i];              // 邻接格子的 y
        if (check(nx, ny) && !vis[nx][ny]) { // 未越界、没掉入黑洞、未访问
            dfs(nx, ny, sx, sy);         // 继续 DFS
        }
    }
}

// 判断把起点选在 (x,y) 的这片连通块（形状）是否“唯一”
// 若在其它某个 '.' 位置也能完整放下同样形状（不越界不撞 'O'）则返回 false，否则 true
bool f(int x, int y) {
    memset(vis, 0, sizeof vis);          // 清空访问标记
    v.clear();                           // 清空形状模板
    dfs(x, y, x, y);                     // 以 (x,y) 为起点，搜出形状（相对位移集合）

    // 在整张图的每个 '.'（排除起点本身）尝试平移放置这个形状
    for (int ii = 0; ii < n; ii++) {     // 枚举行
        for (int j = 0; j < m; j++) {    // 枚举列
            if (s[ii][j] == '.' && (ii != x || j != y)) { // 其他一个空位作为形状新起点
                bool falg = true;        // 假设能完整放下
                for (int i = 0; i < (int)v.size(); i++) { // 遍历形状中的每个相对点
                    int dx = v[i].first; // 取出相对位移 dx
                    int dy = v[i].second;// 取出相对位移 dy
                    int nx = ii + dx;    // 平移后的绝对坐标 x
                    int ny = j + dy;     // 平移后的绝对坐标 y
                    if (!check(nx, ny)) {// 若越界或撞到 'O' 则无法放下
                        falg = false;
                        break;
                    }
                }
                if (falg) return false;  // 找到另一个可行放置点，说明不唯一，返回 false
            }
        }
    }
    return true;                         // 没找到其它可行放置点，说明唯一，返回 true
}

int main() {
    int T;                               // 测试组数
    cin >> T;                            // 读入 T
    while (T--) {                        // 对每组数据
        cin >> n >> m;                   // 读入网格大小 n 行 m 列
        for (int i = 0; i < n; i++) {    // 读入每一行
            cin >> s[i];
        }
        int ans = 0;                     // 本组答案计数（与全局同名，局部遮蔽）
        for (int i = 0; i < n; i++) {    // 枚举每个格子
            for (int j = 0; j < m; j++) {
                // 若该格是 '.' 且以它为起点的形状是唯一的，则计数
                if (s[i][j] == '.' && f(i, j)) {
                    ans++;
                }
            }
        }
        cout << ans << endl;             // 输出本组答案
    }
    return 0;                            // 程序结束
}

*/


#include <bits/stdc++.h>               
using namespace std;
string s[2034];                        // 地图网格，每行一个字符串
int n, m;                                // 网格行数 n、列数 m
int vis[1002][1002];                        // 访问标记（DFS 用），假设 n,m ≤ 50
int dx[4] = { -1, 1, 0, 0 };             // 四联通方向：上、下、右、左 的 x 增量
int dy[4] = { 0, 0, 1, -1 };             // 四联通方向：上、下、右、左 的 y 增量
void bfs(){
    int ans=0,idx=0;
    for(int i=0;i<n;i++){ for(int j=0;j<m;j++){
            if(s[i][j]=='.' && !vis[i][j]){//当前位置是一个。的形式并且当前位置没走过
                idx++;                       int cnt=0;
                queue<pair<int,int>>q;       q.push({0,0});
                vector<pair<int,int>>v;//标记路径
                vis[i][j] = idx;
                while(q.size()){
                    int x=q.front().first,    y=q.front().second;    q.pop();
                    v.push_back({x,y});
                    cnt++;
                    x+=i;y+=j;//现在需要判断的位置
                    for(int k=0;k<4;k++){
                        int nnx = x+dx[k];    int nny = y+dy[k];
                        if(nnx<0 || nnx>=n || nny<0 || nny>=m || s[nnx][nny] != '.' || vis[nnx][nny])continue;
                        vis[nnx][nny] = idx;//可以通过操作将当前位置消去
                        q.push({nnx - i ,nny - j});
                    }
                }int ok = 1;
                for(int ii=0;ii<n;ii++){for(int jj=0;jj<m;jj++){
                        if(s[ii][jj]=='O' || vis[ii][jj] == idx)continue;
                        int flag=1;//标记一下当前 ii jj这个数是否消失
                        for(auto [dx,dy] : v){
                            int a=ii+dx;
                            int b=jj+dy;
                            if(a<0 || a>=n ||b<0 ||b>=m || s[a][b]=='O'){flag=0;break;}
                        }
                        if(flag){ok = 0;break;}//所有情况都判断了还没消失
                    }
                    if(!ok)break;
                }
                if(ok)ans+=cnt;
            }
        }
    }
    cout<<ans<<endl;
}

int main() {
    int T;                               // 测试组数
    cin >> T;                            // 读入 T
    while (T--) {                        // 对每组数据
        cin >> n >> m;                   // 读入网格大小 n 行 m 列
        for (int i = 0; i < n; i++) {    // 读入每一行
            cin >> s[i];
        }
        memset(vis,0,sizeof vis);
        bfs();
    }
    return 0;                            
}

第四题

/*
#include<bits/stdc++.h>
using namespace std;
int a[200041],n,m;
void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cin>>m;
    int h[10086]={0};
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        h[x]++;
    }
    int ans=0;
    bool st=true;
    while(st){
        st=false;
        int z=a[ans%n];//此次攻击是多少的伤害
        ans++;
        if(h[z]){//如果存在z点生命的怪物，攻击掉它
            h[z]--;
            st=true;
        }else if(z==2 && h[1]>0){
            h[1]--;
            st=true;
        }
        else if(h[2*z]){
            h[2*z]--;
            h[z]++;
            st=true;
        }
        else if(h[3*z]){// z=2 3
            h[3*z]--;//6 血僵尸少了一只 9
            h[2*z]++;//4 血僵尸多啦一只 6
            st=true;
        }else{
            for(int i=6;i>0;i--){
                if(h[i]){
                    h[i]--;
                    st=true;
                    h[max(i-z,0)]++;
                    break;
                }
            }
        }
        
    }
    cout<<ans - 1<<endl; 
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
*/
/*
#include<bits/stdc++.h>
using namespace std;
int a[200041],n,m;
int b[200041];
void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    if(n==1){
        cin>>m;
        long long ans=0;
        for(int i=1;i<=m;i++){
            long long x;
            cin>>x;
            ans+=ceil(x*1.0/a[0]);
        }
        cout<<ans<<endl;
        return ;
    }
    cin>>m;
    int h[10086]={0};
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        h[x]++;
    }
    int ans=0;
    bool st=true;
    while(st){
        st=false;
        int z=a[ans%n];//此次攻击是多少的伤害
        ans++;
        if(h[z]){//如果存在z点生命的怪物，攻击掉它
            h[z]--;
            st=true;
        }else if(z==2 && h[1]>0){
            h[1]--;
            st=true;
        }
        else if(h[2*z]){
            h[2*z]--;
            h[z]++;
            st=true;
        }
        else if(h[3*z]){// z=2 3
            h[3*z]--;//6 血僵尸少了一只 9
            h[2*z]++;//4 血僵尸多啦一只 6
            st=true;
        }else{
            for(int i=6;i>0;i--){
                if(h[i]){
                    h[i]--;
                    st=true;
                    h[max(i-z,0)]++;
                    break;
                }
            }
        }
        
    }
    cout<<ans - 1<<endl; 
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
*/

// d {2,3}
// k = [x/n]
// s = k * s[n][2] + s[r][2]
// s = k * s[n][3] + s[r][3]
// 1. 3优先攻击 奇数并且>1 ,将其打为偶数
// 2. 如果是3的倍数，全部使用3清理
// 3. 如果还有3剩余，继续对所有的 bi > 3 每个减3
// 4. 把剩余的3 看做为一个2 合并处理
// 5. 2去清理血量是偶数的部分，最后处理1

//二分答案
#include<bits/stdc++.h>
using namespace std;
long long a[200041],n,m;
long long b[200041];
long long c[200012];//复原血量
long long s[200042][5];// 一直取道第i个数有几个j
long long sum=0;
bool check(long long x){
    long long k=x/n,yu=x%n;
    long long s1=0;
    long long s2=k*s[n][2]+s[yu][2];
    long long s3=k*s[n][3]+s[yu][3];
    for(int i=1;i<=m;i++){
        c[i]=b[i];
        //b[i]&1 也是就是判断b[i]是奇数 (b[i]%2 == 1)
        if(s3&&(b[i]&1) && (b[i]>1) )b[i]-=3,s3--;//3攻击的数量-1 
    }
    if(s3){
        for(int i=1;i<=m;i++){
            if((b[i]/6)*2 <= s3){ // 打6血。保持偶数
                s3-=(b[i]/6)*2;
                b[i]%=6;
            }else{
                b[i]-=6*(s3/2);
                s3%=2;
                break;
            }
        }
    }
    if(s3){//可以还有残留的单个的3点攻击,或者前面的全部小于6
        for(int i=1;i<=m;i++){
            if(b[i]>3){
                b[i]-=3;
                s3--;
                if(s3==0)break;
            }
        }
    }
    s2+=s3;s3=0;//将所有的s3当作s2花掉
    if(s2){
        for(int i=1;i<=m;i++){
            if((b[i]/2) <= s2){ // 打6血。保持偶数
                s2-=(b[i]/2);
                b[i]%=2;
                if(s2==0)break;
            }else{
                b[i]-=s2*2;
                s2=0;
                break;
            }
        }
    }
    if(s2){
        for(int i=1;i<=m;i++){//寻找是1的部分，用s2去送机掉
            if(b[i]&&s2){
                b[i]=0;
                s2--;
                if(s2==0)break;
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(b[i]>0)s1++,b[i]=0;//统计血量不为0的数量
    }
    for(int i=1;i<=m;i++){
        b[i]=c[i];//讲僵尸的原本血量复原
    }
    return s1==0;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            for(int j=2;j<=3;j++){
                s[i][j] = s[i-1][j] + (a[i]==j);
            }
        }
        cin>>m;
        for(int i=1;i<=m;i++){
            cin>>b[i];
        }
        sum=2*s[n][2]+3*s[n][3];
        long long l=1;
        long long r=1e14;
        long long ans=0;
        while(l<=r){
            long long mid = l+r >>1;
            if(check(mid)){//判断当前的攻击量是否够
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        cout<<ans<<endl;
    }
}