本场链接:AtCoder Beginner Contest 192
A - Star
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
int main()
{
int x;cin >> x;
int res = 0;
while(x % 100) ++res,++x;
cout << (res == 0 ? 100 : res) << endl;
return 0;
}
B - uNrEaDaBlE sTrInG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 1005;
char s[N];
int main()
{
scanf("%s",s + 1);int n = strlen(s + 1);
bool ok = 1;
for(int i = 1;i <= n;i += 2) if(s[i] >= 'A' && s[i] <= 'Z') ok = 0;
for(int i = 2;i <= n;i += 2) if(s[i] >= 'a' && s[i] <= 'z') ok = 0;
if(!ok) puts("No");
else puts("Yes");
return 0;
}
C - Kaprekar Number
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
void divide(vector<int>& res,int n)
{
res.clear();
while(n)
{
res.push_back(n % 10);
n /= 10;
}
reverse(res.begin(),res.end());
}
int gback(vector<int>& o)
{
int res = 0;
for(int i = 0;i < o.size();++i)
res = 10 * res + o[i];
return res;
}
int main()
{
int n,k;scanf("%d%d",&n,&k);
vector<int> dup,ddw;
forn(i,1,k)
{
divide(dup,n);
sort(dup.begin(),dup.end());
ddw = dup;
reverse(ddw.begin(),ddw.end());
n = gback(ddw) - gback(dup);
}
printf("%d",n);
return 0;
}
D - Base n
以进制\(p\)表示的数,是随着\(p\)的增大而增大的,具有单调性.可以对最大的\(p\)二分.特判:没有任何一种情况符合时需要让求出的左边界往左挪一位.对于一个数的等价于十进制下判断.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
ll M;
bool check(string& s,ll p)
{
ll res = 0;
for(auto& v : s)
{
if(res > M / p) return 0;
res *= p;
res += v - '0';
}
return res <= M;
}
int main()
{
string x;cin >> x;
cin >> M;
if(x.size() == 1)
{
cout << check(x,10);
return 0;
}
int d = 0;
for(auto& v : x) d = max(d,v - '0');
++d;
ll l = d,r = 2e18;
while(l < r)
{
ll mid = l + r + 1 >> 1;
if(check(x,mid)) l = mid;
else r = mid - 1;
}
if(!check(x,l)) --l;
printf("%lld",l - d + 1);
return 0;
}
E - Train
模型就是一个最短路,考虑怎么解决本题:事实上就是把拓展距离的大小换了一下求的办法,不影响dijkstra正确性.
注意特判一些情况.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
typedef pair<ll,int> pli;
#define x first
#define y second
const int N = 1e5+7,M = 2 * N;
const ll INF = 1e18;
int edge[M],succ[M],stt[M],ett[M],ver[N],idx;
ll dist[N];
bool st[N];
int n,m,STT,EDD;
void add(int u,int v,int w1,int w2)
{
edge[idx] = v;
ett[idx] = w1;
stt[idx] = w2;
succ[idx] = ver[u];
ver[u] = idx++;
}
ll dijkstra(int STT,int EDD)
{
priority_queue<pli,vector<pli>,greater<pli>> pq;
forn(i,1,n) dist[i] = INF;
pq.push({0,STT});dist[STT] = 0;
while(!pq.empty())
{
auto _ = pq.top();pq.pop();
ll d = _.x;int u = _.y;
if(st[u]) continue;
st[u] = 1;
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
ll cost = ett[i] + (d == 0 ? 0 : stt[i] - (d % stt[i] == 0 ? stt[i] : d % stt[i]));
if(dist[v] > d + cost)
{
dist[v] = d + cost;
pq.push({dist[v],v});
}
}
}
return dist[EDD] == INF ? -1 : dist[EDD];
}
int main()
{
memset(ver,-1,sizeof ver);
scanf("%d%d%d%d",&n,&m,&STT,&EDD);
forn(i,1,m)
{
int u,v,w1,w2;scanf("%d%d%d%d",&u,&v,&w1,&w2);
add(u,v,w1,w2);add(v,u,w1,w2);
}
printf("%lld",dijkstra(STT,EDD));
return 0;
}
F - Potion
考虑dp.
状态:\(f[i][j][k]\)表示在前\(i\)个数中选出\(j\)个数时,和模\(j\)的结果是\(k\)的最大和是多少.
接下来考虑如何转移:可以发现如果直接简单的枚举,那么和取模的结果比较难算.更好的处理办法是直接做多次dp,每次强制限制选出的个数是\(C\).最后统计答案.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 105;
ll f[N][N][N],a[N];
inline void chmax(ll& res,ll tar)
{
res = max(res,tar);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
ll n,target;cin >> n >> target;
forn(i,0,n - 1) cin >> a[i];
ll res = 2e18;
forn(C,1,n)
{
forn(i,0,n) forn(j,0,C) forn(k,0,C) f[i][j][k] = -1e18;
f[0][0][0] = 0;
forn(i,0,n - 1) forn(j,0,C) forn(k,0,C - 1)
{
chmax(f[i + 1][j][k],f[i][j][k]);
if(j < C) chmax(f[i + 1][j + 1][(k + a[i]) % C],f[i][j][k] + a[i]);
}
if(f[n][C][target % C] < 0) continue;
res = min(res,(target - f[n][C][target % C]) / C);
}
cout << res;
return 0;
}