(C) Wrong Addition
题意
定义一种计算方式, 对于a+b=c, 给出a和c, 求b
题解
因为求法是从个位求得, 先求出来的最后输出, 符合栈的存储方式, 所以b用栈来存
每次拿c的最后一位(若小于a最后一位, 则取后两位)减去a的最后一位, 存入b的栈
需要注意的是,: 1.若c已经没了, 但是a还有, 则无解
2. 若c中出现00则无解(下面代码中, 以c后两位<a最后一位判断的)
3. 减去后有两位数, 因为每次求出来的只能是b的一个数字
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 1e6+10;
int a[N];
int main()
{
int t;
cin >> t;
while(t --)
{
string s, a;
bool f = 1;
stack<int> c;
cin >> a >>s;
for(int i = a.size()-1, j = s.size()-1; j >= 0; i --, j --)
{
int aa = i>=0?a[i]-'0':0;
int ss = s[j]-'0';
if(ss<aa)
{
if(j==0)
{f=0; break;}//这里是防止下面越界
ss =( s[--j]-'0')*10 + ss;
if(ss<aa){f=0; break;}
}
if(ss-aa>=10){f=0; break;}//减去后有两位数
c.push(ss-aa);
if(j==0&&i>j){f=0; break;}
}
if(!f)puts("-1");
else
{
LL x = 0;
while(c.size())
{
x=(LL)c.top()+x*(LL)10;
c.pop();
}
cout << x<<'\n';
}
}
return 0;
}
D. New Year's Problem
题意
输入顺序是先m后n
张三有 n 个朋友，要在 m 个商店中选一些商店给他的朋友买礼物(最多选n − 1个商店)，要求每个朋友都要收到礼物。
要求最大化 min(每个朋友获得的礼物价值)
题解--二分
对于每个商店--行 : 至少有一个店有两个 礼物>=所枚举的mid, 且最后礼物>=所枚举的mid的礼物总数>=n
对于每个朋友--列 : 每个朋友至少有一个礼物
符合以上条件check函数就完成了
本题学到了对于n*m<=2e5存储的刁钻方法
vector<vector<int> > a(m, vector<int>(n));//定义
bool check(int x, vector<vector<int>> &a)//传入地址
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 2e5+10;
int m, n;
bool check(int x, vector<vector<int>> &a)
{
int ff=0;int f = 0;
for(int i = 0; i < m; i ++)
{
int b=0;
for(int j = 0; j < n; j ++)
{
if(a[i][j]>=x)f ++, b++;
}
if(b>1)ff=1;
}
if(!ff || f<n)return 0;
for(int j = 0; j < n; j ++)
{
int f = 0;
for(int i = 0; i < m; i ++)
{
if(a[i][j]>=x)f ++;
}
if(!f)return 0;
}
return 1;
}
int main()
{
int t;
cin >> t;
while(t --)
{
cin >> m >> n;
vector<vector<int> > a(m, vector<int>(n));
for(int i = 0; i < m; i ++)
for(int j = 0; j <n; j ++)
cin>> a[i][j];
int l = 0, r = 1e9;
while(l < r)
{
int mid = l+r+1>>1;
if(check(mid, a))l = mid;
else r = mid-1;
}
cout <<l<<endl;
}
return 0;
}
E. MEX and Increments(比D简单)
题意
给一串数, 求出当mex=0~n是需要的最小操作数
每一操作可以选择一个数+1, 注: mex=数组中未包含的最小非负整数
题解
对于mex=i时, 输出=数组内i的个数+x
x=补齐1~i-1所需的操作数
多余的数放入优先队列就行了, 每次出来最大的数, 这样差值最小
本题又复习了优先队列好耶!
priority_queue<int, vector<int>> heap;//大到小 priority_queue<int, vector<int>, greater<int>> heap;//小到大
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int a[N], b[N], c[N];
int main(){
int t;
cin >> t;
while(t --)
{
int n;
cin >> n;
for(int i = 0;i <= n ; i++) b[i]=0;
for(int i = 0;i < n ; i++) cin >> a[i], b[a[i]]++;
sort(a,a+n);
priority_queue<int, vector<int>> heap;
bool f = 0;
LL x=0, y=0;
for(int i = 0; i <= n; i ++)
{
if(i && y<i)
{
f = 1;
for(int j = i; j <= n; j ++)cout <<"-1 ";
break;
}
else
{
if(a[i]<=i)
y++;
if(i && b[i-1]==0)
{
int t = heap.top();
heap.pop();
x += i-1-t;
}
if(b[i]>1)
for(int j = 2; j <= b[i]; j ++)heap.push(i);//多余的数进队
cout << x+b[i]<<' ';
}
}
cout << endl;
}
return 0;
}