刷题的第三十天

今天做了三道笔试题。。。都好难啊

1. 选择客栈

丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0∼k−1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p。

他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。

输入

• 第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；
• 接下来的 n 行，第i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。

输出

• 输出只有一行，一个整数，表示可选的住宿方案的总数。

分析：

按照题目要求的进行模拟，每次选择两个进行判断，若满足以下条件：

• 两个客栈的色调相同
• 两个客栈中间（包含两个客栈）中存在一家咖啡店最低消费小于等于p的即算作一个满足条件的解

对于每一个客栈，考虑和当前点前面的客栈进行配对。预处理出pre表示i点（包含i点）前面的第一个<=p的客栈。对于每一个颜色，求出sum表示前i个点有多少个点的颜色等于当前枚举的颜色。依次枚举每一个客栈，若当前客栈最低消费<=p，当前客栈可以和前面任意一个客栈进行匹配，并且pre一定等于i，所以答案可以累加sum[pre]-1；对于当前客栈最低消费>p，则当前客栈只能和pre以及之前的客栈进行匹配，故答案可以累加sum[pre]。

模拟过程：

• 发现第一个满足消费要求的点，那么前面记录的color全部进入sum，这样，只要这个点后面有color相同的点，就多了sum种住宿方案（更新ans），此时，要将前面的color全部清零。
• 发现第二个满足消费要求的点，那么在两个点之间的color全部进入sum（记作sum（新）），这样，只要这个点后面有color相同的点，那么就多了sum（新）种住宿方案（更新ans），此时color再次清零，之后同理。

#include<stdio.h>
const int MX=200001;
int cnt[MX],last[MX],sum[MX],n,k,p,now;

int main()
{
    
    int ans=0;
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;++i)
    {
    
        int color,price;
        scanf("%d%d",&color,&price);
        if(price<=p)
            now=i;
        if(now>=last[color])
            sum[color]=cnt[color];
        last[color]=i;
        ans+=sum[color];
        cnt[color]++;
    }
    printf("%d",ans);
    return 0;
}

2.两数相乘得完全平方数

对于一个序列，牛牛每次可以将序列中任意一个位置上的数乘上任意一个质数。
现在他想知道至少需要多少次操作才能使得该序列中的任意两个不同位置的数相乘都为完全平方数。
完全平方数：对于$x$，若其可以写成的形式$i\times i=x$，则称为$x$完全平方数。
提示：一个数是完全平方数的充要条件是其所有质因子的指数都为偶数。
输入描述：
第一行输入一个整数N，表示序列长度
接下来一行输入N个整数，表示该序列
输出描述：
输出一个整数表示答案

示例：
输入
3
2 1 2
输出
1
说明
只需要将第二个1乘上2即可，这样序列就变为2 2 2，任意两个数相乘都是4

分析：

分解质因数，统计每个因子在每个数中存在的个数为奇数还是偶数。只有偶数次则无需操作；有奇数次，则需判断时候有没有该因子的数，取小的进行操作；奇数偶数次都有，取小的进行操作。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n, x, res;
map<int, int> p1, p2;

void divide(int n)
{
    
    for(int i=2;i<=n/i;i++)
        if(n%i==0)
        {
    
            int s=0;
            while(n%i==0)
            {
    
                n/=i;
                s++;
            }
            if(s % 2) p1[i] ++;
            else p2[i] ++;
        }
    if(n>1) p1[n] ++;
}

int main()
{
    
    cin >> n;
    for(int i = 0; i < n; i ++) 
    {
    
        cin >> x;
        divide(x);
    }
    for(int i = 0; i < 100002; i ++)
    {
    
        if(p1[i] != 0 && p1[i] < n) res += min(p1[i], n - p1[i]);
        else if(p1[i] != 0 && p2[i] != 0) res += min(p1[i], p2[i]);  
    }
    cout << res << endl;
    return 0;
}