A. Square String?

题目描述

如果某个字符串是连续写入两次的字符串,则该字符串称为正方形。 例如,字符串“aa”、“abcabc”、“abab”和“baabaa”是方形的。 但是字符串“aaa”、“abaaab”和“abcdabc”不是方形的。

对于给定的字符串 s 确定它是否是正方形。

输入

输入数据的第一行包含一个整数 t (1≤t≤100)——测试用例的数量。

接下来是 t 行,每行包含一个测试用例的描述。 给定的字符串仅由小写拉丁字母组成,长度介于 1 和 100 之间。

输出

对于每个测试用例,在单独的行上输出:

YES 如果对应测试用例中的字符串是方形的,
否,否则。
在任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应)。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn=1e6+5;
void solve(){
   
    string s;
    cin >> s;
    if(s.length()%2==0){
   
        for (int i = 0; i < s.length() / 2;i++){
   
            if(s[i]!=s[i+s.length()/2]){
   
                cout << "NO\n";
                return;
            }
        }
        cout << "YES\n";
    }else{
   
        cout << "NO\n";
    }
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t ;
    while(t--){
   
         solve();
    }
    return 0;
}

B. Squares and Cubes

题目描述

Polycarp 喜欢正整数的正方形和立方体。 这是他喜欢的数字序列的开头:1, 4, 8, 9, …

对于给定的数字 n,计算 Polycarp 喜欢的从 1 到 n 的整数的数量。 换句话说,找出这样的 x 的数目,即 x 是正整数的平方或正整数的立方(或同时是平方和立方)。

输入

第一行包含一个整数 t (1≤t≤20)——测试用例的数量。

然后 t 行包含测试用例,每行一个。 每行包含一个整数 n ( 1 ≤ n ≤ 1 0 9 ) n (1≤n≤10^9) n(1n109)

输出

对于每个测试用例,打印您正在寻找的答案——Polycarp 喜欢的从 1 到 n 的整数数量。

code:


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

void solve(){
   
    int n;
    cin >> n;
    int cnt = 0;
    map<int,int> a;
    for (int i = 1; i * i <= n;i++){
   
        cnt++;
        a[i * i] = 1;
    }
    for (int i = 1; i * i * i <= n;i++){
   
        if(a[i*i*i]==1){
   
            continue;
        }else
            cnt++;
    }
    cout << cnt << endl;
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t ;
    while(t--){
   
         solve();
    }
    return 0;
}

C. Wrong Addition

题目描述


code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn=1e6+5;
void solve(){
   
    ll a, s, ans = 0; cin >> a >> s;
    ll t = 1;
    
    while(s > 0){
   
        int da = a % 10;
        int ds = s % 10;
 
        s /= 10;
        a /= 10;
 
        if(ds >= da){
   
            ans += t *(ds - da);
        }
        else if(s%10 == 1){
   
            s /= 10;
            ans += t * (10 + ds - da);
        }
        else{
   
            cout << -1 << '\n';
            return;
        }
        t *= 10;
    }
    
    if(a == 0) cout << ans << '\n';
    else cout << -1 << '\n';
    return;
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t ;
    while(t--){
   
         solve();
    }
    return 0;
}

D. New Year’s Problem

题目描述

弗拉德有 n 个朋友,他想为每个朋友买一份新年礼物。

城里有m家商店,他可以在每家商店买礼物送给他的任何一个朋友。如果第 j 个朋友 (1≤j≤n) 收到在商店购买的编号为 i (1≤i≤m) 的礼物,则该朋友收到 p i j p_{ij} pij 单位的快乐。矩形表 p i j p_{ij} pij 在输入中给出。

Vlad 有时间访问最多 n-1 家商店(其中 n 是朋友的数量)。他选择他将访问的商店以及他将在每个商店中为哪些朋友购买礼物。

让第 j 个朋友从弗拉德的礼物中获得 j 个单位的快乐。让我们找到值 α = m i n α=min α=min{ a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an}。 Vlad 的目标是购买礼物,使 α 的值尽可能大。换句话说,弗拉德想要最大限度地减少他朋友的快乐。

例如,设 m=2,n=2。让我们在第一家商店买到的礼物的快乐: p 11 p_{11} p11=1, p 12 p_{12} p12=2,在第二家商店: p 21 p_{21} p21=3, p 22 p_{22} p22=4。

那么 Vlad 只去第二家商店为第一个朋友买礼物就足够了,带来了快乐 3,为第二个朋友带来了快乐 4。在这种情况下,值 α 将等于 min{3, 4}=3
帮助 Vlad 为他的朋友选择礼物,使 α 的值尽可能高。请注意,每位朋友必须收到一份礼物。 Vlad 最多可以访问 n−1 家商店(其中 n 是朋友的数量)。在商店里,他可以购买任意数量的礼物。

输入

输入的第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1t104)——输入中测试用例的数量。

在每个测试用例之前写一个空行。然后有一行包含整数 m m m n ( 2 ≤ n , 2 ≤ n ⋅ m ≤ 1 0 5 ) n (2≤n, 2≤n⋅m≤10^5) n(2n,2nm105),中间用空格隔开——商店数量和朋友数量,其中 n⋅m 是 n 和 m 的乘积。

然后是 m 行,每行包含 n 个数字。第j列第i行的数字 p i j ( 1 ≤ p i j ≤ 1 0 9 ) p_{ij}(1≤p_{ij}≤10^9) pij(1pij109)是店铺号i中朋友j的商品的喜悦程度。

保证测试中所有测试用例的值 n⋅m 的总和不超过 1 0 5 10^5 105

输出

打印 t 行,每行必须包含对应测试用例的答案——α 的最大可能值,其中 α 是给 Vlad 的所有朋友的礼物带来的快乐的最小值。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
const int maxn=1e6+5;
void solve(){
   
    ll n, m;
    cin >> m >> n;
    vvl v(m, vl(n));
    for (int i = 0; i < m; i++){
   
        for (int j = 0; j < n;j++)
            cin >> v[i][j];
    }
    ll l = 0, r = 1e9 + 10;
    ll ans = 0;
    while (l <= r){
   
        ll mid = l + (r - l) / 2;
        bool can = false, can1 = false;
        set<ll> st;
        for (int i = 0; i < n; i++){
   
            can = false;
            for (int j = 0; j < m; j++){
   
                if (v[j][i] >= mid){
   
                    can = true;
                    if (st.count(j)){
   
                        can1 = true;
                    }
                    st.insert(j);
                }
            }
            if (!can)
                break;
        }
        if (can && can1){
   
            ans = mid;
            l = mid + 1;
        }
        else{
   
            r = mid - 1;
        }
    }
    cout << ans << endl;
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t ;
    while(t--){
   
         solve();
    }
    return 0;
}

E. MEX and Increments

题目描述

Dmitry 有一个由 n 个非负整数 a1,a2,…,an 组成的数组。

在一次操作中,Dmitry 可以选择任意一个索引 j(1≤j≤n)并将元素 aj 的值增加 1。他可以多次选择相同的索引 j。

对于从 0 到 n 的每个 i,确定 Dmitry 是否可以使数组的 MEX 恰好等于 i。如果可能,则确定执行此操作的最少操作次数。

数组的 MEX 等于不在数组中的最小非负整数。例如数组[3,1,0]的MEX等于2,数组[3,3,1,4]的MEX等于0。

输入

输入数据的第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1t104)——输入中测试用例的数量。

测试用例的描述如下。

每个测试用例描述的第一行包含一个整数 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n (1≤n≤2⋅10^5) n(1n2105)——数组 a 的长度。

每个测试用例描述的第二行包含 n 个整数 a 1 , a 2 , … , a n ( 0 ≤ a i ≤ n ) a_1,a_2,…,a_n (0≤a_i≤n) a1,a2,,an(0ain)——数组 a 的元素。

保证测试中所有测试用例的值 n 的总和不超过 2 ⋅ 1 0 5 2⋅10^5 2105

输出

对于每个测试用例,输出 n+1 个整数——第 i 个数字等于您可以使数组 MEX 等于 i ( 0 ≤ i ≤ n ) i (0≤i≤n) i(0in) 的最小操作数,如果不能这样做,则为 -1 .

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 1e6 + 5;
int a[maxn],cnt[maxn],num[maxn];
set<int>st;
void solve()
{
   
    int n;
		cin >> n;
		for (int i = 0 ; i <= n ; i ++)
		{
   
			cnt[i] = 0;
			num[i] = 0;
		}
		for (int i = 1 ; i <= n ; i ++)
		{
   
			cin >> a[i];
			cnt[a[i]] ++;
		}
		ll ans = 0;
		int pos = -1;
		int sum = 0;
		st.clear();
		for (int i = 0 ; i <= n ; i ++)
		{
   
			if (sum < i) ans = -1;
			if (ans == -1)
			{
   
				cout<<ans<<" ";
				continue;
			}
			sum += cnt[i];
			ans += cnt[i];
			if (i > 0) 
			{
   
				if (cnt[i - 1]) ans -= cnt[i - 1];
				else 
				{
   
					auto it = st.end();
					it --;
					while(st.size() && num[(*it)] == 0)
					{
   
						st.erase(it);
						it = st.end();
						it --;
					}
					ans += (i - 1) - ((*it) + 1) + 1;
					num[*it] --;
				}
			}
			if (cnt[i] >= 2) 
			{
   
				st.insert(i);
				num[i] = cnt[i] - 1;
			}
			cout<<ans<<" ";
		}
		cout<<endl;
}

int main()
{
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
    {
   
        solve();
    }
    return 0;
}