19级算法训练赛第十场
比赛地址：https://vjudge.net/contest/367058#overview 密码：IWantToACC
内容涉及：A数学定理 B贪心入门 C枚举or数位dp D枚举or唯一分解定理 E离散化+差分 F唯一分解定理 G计算机常识+二进制 H签到
直播讲解高清录像放在B站上，点击下面链接进入
视频链接：https://www.bilibili.com/video/bv1ak4y197pm
A-[NOIP2017]小凯的疑惑
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int main(){
ios;
ll a,b;cin>>a>>b;
cout<<a*b-(a+b)<<endl;
return 0;
}B-合并果子
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;
int T,N;
priority_queue<int,vector<int>,greater<int>> q;
int main(){
ios;
cin>>T;
while(T--){
while (q.size()) q.pop();
cin>>N;
for(int i = 1;i<=N;i++){
int cur;cin>>cur;
q.push(cur);
}
ll res = 0;
while(q.size()>=2){
int t1 = q.top();q.pop();
int t2 = q.top();q.pop();
res += t1 + t2;
q.push(t1+t2);
}
cout<<res<<endl;
}
return 0;
}C - 不要62
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;
int N,M;
int dp[maxn][2];
int nums[10];
int dfs(int pos,bool limit,bool pre_is6){
if(!limit && dp[pos][pre_is6] != -1) return dp[pos][pre_is6];
if(pos == 0) return 1;
int up = limit? nums[pos]:9;
int sum = 0;
for(int i = 0;i<=up;i++){
if(i == 4) continue;
if(i == 2 && pre_is6) continue;
sum += dfs(pos-1,limit && i == nums[pos],i == 6);
}
if(!limit) dp[pos][pre_is6] = sum;
return sum;
}
int solve(int x){
int pos = 0;
while(x){
nums[++pos] = x%10;
x/=10;
}
return dfs(pos,1,0);
}
int main(){
memset(dp,-1, sizeof(dp));
while(scanf("%d %d",&N,&M)){
if(N == 0 && M == 0) break;
printf("%d\n",solve(M)-solve(N-1));
}
return 0;
}D - [NOIP2009]Hankson的趣味题
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;
int T;
int a0,a1,b0,b1;
bool vis[maxn];
int P[maxn],tail;
struct node{
int a,b,c,d;
};
map<int,node> mp;
inline void read(int &x){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
inline void write(int X)
{
if(X<0) {putchar('-'); X=~(X-1);}
int s[20],top=0;
while(X) {s[++top]=X%10; X/=10;}
if(!top) s[++top]=0;
while(top) putchar(s[top--]+'0');
}
void initP(int N){
for(int i = 2;i<=N;i++){
if(!vis[i]) P[tail++] = i;
for(int j = 0;P[j]<=N/i;j++){
vis[P[j]*i] = true;
if(i%P[j] == 0) break;
}
}
}
void divP(){
int idx = 0;
for(int t:{a0,a1,b0,b1}){
++idx;
for(int j = 0;j<tail && P[j]*P[j] <=t;j++){
if(t%P[j] == 0){
int cnt = 0;
while(t%P[j] == 0){
cnt++;
t/=P[j];
}
if(idx == 1) mp[P[j]].a = cnt;
if(idx == 2) mp[P[j]].b = cnt;
if(idx == 3) mp[P[j]].c = cnt;
if(idx == 4) mp[P[j]].d = cnt;
}
}
if(t>1){
if(idx == 1) mp[t].a = 1;
if(idx == 2) mp[t].b = 1;
if(idx == 3) mp[t].c = 1;
if(idx == 4) mp[t].d = 1;
}
}
}
ll fun(){
ll res = 1;
for(auto p:mp){
node cur = p.second;
int a = cur.a,b = cur.b,c = cur.c,d = cur.d;
int cnt = 0;
for(int i = 0;i<=31;i++){
if(min(i,a) == b && max(i,c) == d) cnt++;
}
res *= cnt;
}
return res;
}
int main(){
initP(1<<16);
cin>>T;
while(T--){
read(a0),read(a1),read(b0),read(b1);
mp.clear();
divP();
printf("%d\n",fun());
}
return 0;
}E - Covered Points Count
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 1e6+10;
using namespace std;
int N;
pii lr[maxn];
ll arr[maxn],tail;
ll ca[maxn],idx;
ll ans[maxn];
map<ll,ll> pos,rpos;
void Lisa(){
arr[0] = -1;
sort(arr+1,arr+tail+1);
for(int i = 1;i<=tail;i++){
if(arr[i] != arr[i-1]) pos[arr[i]] = ++idx,rpos[idx] = arr[i];
}
}
int main(){
ios;
cin>>N;
for(int i = 1;i<=N;i++){
ll l,r;cin>>l>>r;
arr[++tail] = l,arr[++tail] = r+1;
lr[i] = {l,r};
}
Lisa();
for(int i = 1;i<=N;i++){
ll l = lr[i].fs,r = lr[i].sc;
ca[pos[l]] += 1;
ca[pos[r+1]] -=1;
}
for(int i = 1;i<=idx;i++) ca[i] += ca[i-1];
for(int i = 1;i<=idx-1;i++){
ans[ca[i]] += rpos[i+1] - rpos[i];
}
for(int i = 1;i<=N;i++) cout<<ans[i]<<" ";cout<<endl;
return 0;
}
F - [NOIP2009]细胞分裂
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int inf = 2e9;
using namespace std;
int N,M1,M2;
bool vis[maxn];
int P[maxn/10],tail;
struct node
{
int a,b;
};
map<int,node> mp;
int ans = inf;
void initP(int N){
for(int i = 2;i<=N;i++){
if(!vis[i]) P[tail++] = i;
for(int j = 0;P[j]<=N/i;j++){
vis[P[j] * i] = true;
if(i % P[j] == 0) break;
}
}
}
void divM(int x = M1){
for(int i = 0;i<tail && P[i]*P[i] <= x;i++){
if(x%P[i] == 0){
int cnt = 0;
while(x%P[i] == 0){
cnt++;
x/=P[i];
}
mp[P[i]].b = cnt * M2;
}
}
if(x>1) mp[x].b = M2;
}
void divP(int x){
mp.clear();
divM();
for(int i = 0;i<tail && P[i]*P[i] <= x;i++){
if(x%P[i] == 0){
int cnt = 0;
while(x%P[i] == 0){
cnt++;
x/=P[i];
}
mp[P[i]].a = cnt;
}
}
if(x>1) mp[x].a = 1;
}
int sovle(){
int mx = 0;
for(auto p:mp){
auto cur = p.second;
int a = cur.a,b = cur.b;
if(b > 0 && a == 0) return inf;
if(b > 0) mx = max(mx,(b-1)/a + 1);
}
return mx;
}
int main(){
ios;
initP(1<<16);
cin>>N>>M1>>M2;
while(N--){
int x;cin>>x;
divP(x);
ans = min(ans,sovle());
}
if(ans == inf) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}G - 输出二进制补码
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;
vector<bool> ans;
int main(){
ios;
int N;cin>>N;
for(int j = 31;j>=0;j--){
if((N>>j)&1) ans.push_back(1);
else ans.push_back(0);
}
for(int i = 0;i<32;i++) cout<<ans[i];
return 0;
}H - 矩阵加法
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;
int N,M;
int ans[111][111];
int main(){
ios;
cin>>N>>M;
for(int k:{1,2}){
for(int i = 1;i<=N;i++){
for(int j = 1;j<=M;j++){
int cur;cin>>cur;
ans[i][j] += cur;
}
}
}
for(int i = 1;i<=N;i++){
for(int j = 1;j<=M;j++){
cout<<ans[i][j];
if(j<M) cout<<" ";
}
cout<<endl;
}
return 0;
}
京公网安备 11010502036488号