The 2018 ACM-ICPC Asia Qingdao Regional Contest
The 2018 ACM-ICPC Asia Qingdao Regional Contest
C - Flippy Sequence
#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 pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int maxn = 2e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
template<class T>void read(T &x){
T 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;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class T>void print(T x){
cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
print(h);
print(t...);
}
ll T,N;
char a[maxn],b[maxn];
ll solve(){
vector<pii> LR;
LR.clear();
ll l = -1,r = -1;
for(int i = 1;i<=N;i++){
if(a[i] != b[i]){
if(l == -1) l = i,r = i;
else r = i;
}else{
if(l != -1 && r != -1){
LR.pb({l,r});
l = -1,r = -1;
if(LR.size()>=3) return 0;
}
}
}
if(l != -1 && r != -1) LR.pb({l,r});
if(LR.size()>=3) return 0;
else if(LR.size()==0) return N*(N+1)/2;
else if(LR.size()==1){
ll l = LR[0].fs,r = LR[0].sc;
ll ans = (r-l)*2;
ans += (l-1)*2 + (N-r)*2;
return ans;
}else{
return 6LL;
}
}
int main(){
// debug;
read(T);
while(T--){
read(N);
scanf("%s",a+1);
scanf("%s",b+1);
ll ans = solve();
printf("%lld\n",ans);
}
return 0;
}D - Magic Multiplication
#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 pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
template<class T>void read(T &x){
T 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;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class T>void print(T x){
cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
print(h);
print(t...);
}
int T,N,M;
char c[2*maxn];int len;
int a[maxn],b[maxn];
bool judge(int s){
for(int i = 1;i<=N;i++) a[i] = 0;
for(int i = 1;i<=M;i++) b[i] = 0;
a[1] = s;
int idxa = 1,idxb = 1,pos = 1;
for(int j = 1;j<=M;j++){
if(a[1] <= c[pos]-'0' || c[pos] == '0'){
if(pos>len) return false;
int cur = c[pos] - '0';
if(cur%a[1]) return false;
b[j] = cur/a[1];
pos++;
}else{
if(pos>len-1) return false;
int cur = 10*(c[pos] - '0') + c[pos+1]-'0';
if(cur%a[1]) return false;
b[j] = cur/a[1];
pos+=2;
}
}
// for(int j= 1;j<=M;j++) printf("%d",b[j]);printf("\n");
while(1){
if(pos>len) break;
int cur_ans = -1;
for(int j = 1;j<=M;j++){
if(pos>len || idxa >=N) return false;
int cur = c[pos]-'0';
if(cur>=b[j] || cur == 0){
if(cur>0 && b[j] == 0) return false;
else if(cur == 0 && b[j] == 0){
;
}else{
if(cur%b[j]) return false;
if(cur_ans == -1) cur_ans = cur/b[j];
else if(cur_ans == cur/b[j]) ;
else return false;
}
pos += 1;
}else{
if(pos>len-1) return false;
cur = cur*10 + c[pos+1]-'0';
if(cur%b[j]) return false;
if(cur_ans == -1) cur_ans = cur/b[j];
else if(cur_ans == cur/b[j]) ;
else return false;
pos += 2;
}
}
a[++idxa] = cur_ans;
if(idxa > N) return false;
}
if(idxa != N) return false;
return true;
}
void solve(){
int ok = 0;
for(int i = 1;i<=9;i++){
if(judge(i)){
ok = 1;
break;
}
}
if(!ok) puts("Impossible");
else{
for(int i = 1;i<=N;i++){
if(a[i] == -1) printf("0");
else printf("%d",a[i]);
}
printf(" ");
for(int i = 1;i<=M;i++) printf("%d",b[i]);printf("\n");
}
}
int main(){
// debug;
read(T);
while(T--){
read(N,M);
scanf("%s",c+1);len = strlen(c+1);
solve();
}
return 0;
}E - Plants vs. Zombies
#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 pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
template<class T>void read(T &x){
T 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;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class T>void print(T x){
cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
print(h);
print(t...);
}
ll T,N,M;
ll a[maxn];
ll d[maxn];
bool judge(ll mid){
for(int i = 1;i<=N;i++) d[i] = 0;
ll t = M,pos = 0;
while(1){
if(pos >N) break;
if(t<=0) break;
if(pos == 0 && t>0) {
pos++;
d[pos] += a[pos];
t--;
}else{
if(d[pos] < mid){
ll tim = (mid - d[pos] + a[pos] - 1)/a[pos];
if(2*tim > t) return false;
d[pos] += a[pos] * tim;
d[pos+1] += a[pos+1] * tim;
t -= 2*tim;
}
if(t>0 && pos<=N){
pos++;
d[pos] += a[pos];
t--;
}
}
}
for(int i = 1;i<=N;i++) if(d[i] < mid) return false;
return true;
}
void solve(){
ll l = 0,r = 1e18+100,ans;
while(l<=r){
ll mid = (l+r)>>1;
if(judge(mid)) l = mid+1,ans = mid;
else r = mid-1;
}
printf("%lld\n",ans);
}
int main(){
// debug;
read(T);
while(T--){
read(N,M);
for(int i = 1;i<=N;i++) read(a[i]);
solve();
}
return 0;
}J - Books
#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 pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
template<class T>void read(T &x){
T 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;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class T>void print(T x){
cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
print(h);
print(t...);
}
int T,N,M;
int a[maxn];
void solve(){
int t1 = M,t2 = 0;
for(int i = 1;i<=N;i++) if(a[i] <= 0) t2++;
if(t2>t1) puts("Impossible");
else if(t1 == 0){
int mi = 1e9+10;
for(int i = 1;i<=N;i++) mi = min(mi,a[i]);
printf("%d\n",mi-1);
}else{
if(t1 == N) puts("Richman");
else{
t1 -= t2;
ll ans = 0,ok = 1;
for(int i =1;i<=N;i++){
if(t1>0){
if(a[i] != 0) {
ans += a[i];
t1--;
}
}else{
int mi = 1e9+10;
for(int j = i;j<=N;j++){
if(a[j] != 0) mi = min(mi,a[j]);
}
ans += mi-1;
break;
}
}
printf("%lld\n",ans);
}
}
}
int main(){
// debug;
read(T);
while(T--){
read(N,M);
for(int i = 1;i<=N;i++) read(a[i]);
solve();
}
return 0;
}M - Function and Function
#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 pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
template<class T>void read(T &x){
T 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;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class T>void print(T x){
cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
print(h);
print(t...);
}
int T,x,k;
int a[100];
void init(){
a[1] = a[2] = a[3] = a[5] = a[7] = 0;
a[0] = a[4] = a[6] = a[9] = 1;
a[8] = 2;
}
int solve(){
int ans = x;
for(int i = 1;i<=k;i++){
int tmp = ans;
int tmp2 = 0;
if(tmp == 0){
int left = k-i+1;
if(left%2) return 1;
else return 0;
}else{
while(tmp){
tmp2 += a[tmp%10];
tmp/=10;
}
}
if(tmp2 == ans) break;
ans = tmp2;
}
return ans;
}
int main(){
// debug;
init();
read(T);
while(T--){
read(x,k);
int ans = solve();
printf("%d\n",ans);
}
return 0;
}Ryuichi的算法分享 文章被收录于专栏
分享我的一些算法题解，致力于把题解做好，部分题解可能会采用视频的形式来讲解。
