The 2024 ICPC Asia EC Regionals Online Contest (II)
目录
- 写在前面
- F 签到
- A 枚举
- J 贪心
- I 构造，二进制
- L 数学，三分
- G 数学，辗转相除
- E 结论，最短路
- 写在最后
写在前面
补题地址：https://codeforces.com/gym/105358。
以下按个人向难度排序。
妈的 7 题秒完剩下的题感觉没一个能做的。
F 签到
#include <bits/stdc++.h>
#define ll long long
const int N = 1e5 + 5;
ll a[N], n;
int main() {
scanf("%d", &n);
ll ans = 1500;
for(int i = 1; i <= n; ++i)
{
scanf(" %d", &a[i]);
ans += a[i];
if(ans >= 4000)
{
printf("%d\n", i);
return 0;
}
}
printf("-1\n");
return 0;
}
A 枚举
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pr pair
#define mp make_pair
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int kInf = 1e9 + 10;
const int kN = 1e5 + 10;
int num, n, k;
int w[kN], schoolid[kN];
vector<pr <int, int> > team[kN];
map <string, int> id;
set <pr <int, int> > endteam;
int ans[kN];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
int minc = kInf;
for (int i = 1; i <= k; ++ i) {
int c; cin >> c;
minc = min(minc, c);
}
for (int i = 1; i <= n; ++i) {
string school; int x;
cin >> x >> school;
if (!id.count(school)) id[school] = ++ num;
team[id[school]].push_back(mp(-x, i));
w[i] = x;
schoolid[i] = id[school];
}
for (int i = 1; i <= num; ++ i) {
sort(team[i].begin(), team[i].end());
while (team[i].size() > minc) team[i].pop_back();
for (auto x: team[i]) endteam.insert(x);
}
int cnt = 0;
endteam.insert(mp(-1, n + 1));
for (auto x: endteam) {
// cout << x.first << " " << x.second << "\n";
ans[x.second] = ++ cnt;
}
for (int i = 1; i <= n; ++ i) {
if (ans[i]) continue;
auto it = endteam.lower_bound(mp(-w[i], 0));
ans[i] = ans[it->second] - 1;
}
for (int i = 1; i <= n; ++ i) cout << ans[i] << "\n";
return 0;
}
J 贪心
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
ll read()
{
ll x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 1e5 + 5;
int n;
struct node
{
ll w, v, c;
node(){ w = v = c = 0; }
bool friend operator < (const node &a, const node &b)
{ return a.c * b.w < b.c * a.w ; }
}A[N];
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
n = read();
ll V = 0, W = 0;
for(int i = 1; i <= n; ++i)
{
A[i].w = read(), A[i].v = read(), A[i].c = read();
V += A[i].v ;
}
sort(A + 1, A + n + 1);
for(int i = 1; i <= n; ++i) V -= W * A[i].c , W += A[i].w ;
printf("%lld\n", V);
return 0;
}
I 构造，二进制
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
int n,T;
int a[33];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// n=read();
std::cin>>T;
while(T--){
cin>>n;
for(int i=0;i<=31;++i){
if((n>>i)&1) a[i]=1;
else a[i]=0;
}
for(int i=0;i<31;++i){
if(a[i]==1&&a[i+1]==0) a[i+1]=1,a[i]=-1;
}
bool fl=0;
for(int i=0;i<31;++i){
if(a[i]==0&&a[i+1]==0) fl=1;
}
if(fl) cout<<"NO\n";
else{
cout<<"YES\n";
// cout<<a[31]<<endl;
for(int i=1;i<=4;++i){
for(int j=0;j<8;++j){
cout<<a[(i-1)*8+j]<<' ';
}
cout<<'\n';
}
}
}
return 0;
}
L 数学，三分
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
int n;
int t;
double check(int k){
return (double)(k-1.00)/2+(double)t/k;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// n=read();
std::cin>>n;
for(int i=1;i<=n;++i){
cin>>t;
// for(int j=1;j<=t;++j){
// cout<<j<<' '<<check(j)<<'\n';
// }
int lmid, rmid;
int id=1;
double lans, rans,ans=check(1);
for (int l = 1, r = t; l <= r; ) {
lmid = l + (r - l + 1) / 3;
rmid = r - (r - l + 1) / 3;
lans = check(lmid);
rans = check(rmid);
if(ans>lans) id=lmid,ans=lans;
if(ans>rans) id=rmid,ans=rans;
// cout<<lans<<' '<<rans<<' '<<l<<' '<<r<<'\n';
if (lans <= rans) r = rmid - 1;
else l = lmid + 1;
}
for(int j=min(lmid,rmid)-5;j<=max(lmid,rmid)+5;++j){
if(j<1||j>t) continue;
lans = check(j);
if(ans>lans) id=j,ans=lans;
}
// id=13;
int x=id*(id-1)+2*t;
int y=2*id;
int gg=__gcd(x,y);
x/=gg,y/=gg;
cout<<x<<' '<<y<<'\n';
}
return 0;
}
G 数学，辗转相除
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const ll mod = 998244353;
ll qpow(ll a, ll b, ll mod)
{
ll ans = 1;
while(b)
{
if(b & 1) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
ll a0, a1, b, p0, p1, p2;
ll dfs(ll x, ll y)
{
if(x == y) return p0 * p2 % mod;
if(x < y)
{
int k = y / x;
if(y % x == 0) --k;
return dfs(x, y - k * x) * qpow(p0 * p2 % mod, k, mod) % mod;
}else
{
int k = x / y;
if(x % y == 0) --k;
return ((dfs(x - k * y, y) - 1 + mod) % mod * qpow(p1 * p2 % mod, k, mod) % mod + 1) % mod;
}
}
void solve()
{
int x = read(), y = read();
a0 = read(), a1 = read(), b = read();
p0 = a0 * qpow(b, mod - 2, mod) % mod, p1 = a1 * qpow(b, mod - 2, mod) % mod, p2 = (1 - p0 - p1 + mod + mod) % mod;
p2 = qpow((1 - p2 + mod) % mod, mod - 2, mod);
printf("%lld\n", dfs(x, y));
}
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
int T = read();
while(T--) solve();
return 0;
}
E 结论，最短路
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
const int M=2e6+5;
const int inf=1e18;
#define ll long long
#define ull unsigned long long
int T,n,m,d,k;
int id[N][2];
int s[N];
int lim[N][2],tot,head[N*2];
int f[N][2],pre[N][2];
int p[N*4],L,R;
struct node{
int to,nxt;
}e[M<<1];
void add(int u,int v){
e[++tot].to=v,e[tot].nxt=head[u],head[u]=tot;
}
void get_new(bool fl,int now,int u,int v){
// if(u==3){
// cout<<"!!\n";
// cout<<fl<<' '<<now<<' '<<u<<' '<<v<<endl;
// }
if(lim[u][fl]>now&&f[u][fl]==inf){
// cout<<u<<endl;
f[u][fl]=now;
pre[u][fl]=v;
if(fl) p[++R]=u+n;
else p[++R]=u;
}
}
int ans[N*4][2],la[2];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>T;
while(T--){
cin>>n>>m>>d;
for(int i=1;i<=n;++i) id[i][0]=i,id[i][1]=n+i;
for(int i=0;i<=n;++i){
f[i][0]=f[i][1]=lim[i][0]=lim[i][1]=inf;
pre[i][0]=0;
pre[i][1]=0;
}
tot=0;
for(int i=1;i<=2*n;++i) head[i]=0;
for(int i=1,u,v;i<=m;++i){
cin>>u>>v;
add(u,v),add(v,u);
// add(id[u][0],id[v][1]);
// add(id[u][1],id[v][0]);
// add(id[v][1],id[u][0]);
// add(id[v][0],id[u][1]);
}
cin>>k;
for(int i=1;i<=k;++i){
cin>>s[i];
p[i]=id[s[i]][0];
lim[s[i]][0]=0;
}
L=1,R=k;
while(L<=R){
int u=p[L];
++L;
bool fl=0;
if(u>n) fl=1,u-=n;
// cout<<u<<' '<<fl<<'\n';
int now=lim[u][fl];
if(now>=d) continue;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
// cout<<v<<"!!!\n";
// cout<<lim[v][!fl]<<endl;
if(lim[v][!fl]==inf){
lim[v][!fl]=now+1;
p[++R]=id[v][!fl];
}
}
}
// lim done
// for(int i=1;i<=n;++i){
// cout<<i<<' '<<lim[i][0]<<' '<<lim[i][1]<<'\n';
// }
L=1,R=0;
get_new(0,0,1,0);
// cout<<f[1][0]<<' '<<f[1][1]<<"askljdsjlak"<<endl;
while(R>=L){
int u=p[L];
++L;
bool fl=0;
if(u>n) fl=1,u-=n;
// cout<<u<<' '<<fl<<"!!!\n";
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
// cout<<v<<"???????\n";
int now=f[u][fl]+1;
get_new(!fl,now,v,u);
}
}
la[0]=la[1]=inf;
for(int ty=0;ty<=1;++ty){
int tmp=ty,now=n;
if(f[n][ty]!=inf){
la[ty]=1;
while(now){
ans[la[ty]][ty]=now;
now=pre[now][tmp];
++la[ty];
tmp=!tmp;
}
}
}
if(la[0]==inf&&la[1]==inf){
cout<<-1<<'\n';
continue;
}
if(la[0]>la[1]){
cout<<la[1]-2<<'\n';
for(int i=la[1]-1;i>=1;--i){
cout<<ans[i][1]<<' ';
} cout<<'\n';
}else{
cout<<la[0]-2<<'\n';
for(int i=la[0]-1;i>=1;--i){
cout<<ans[i][0]<<' ';
} cout<<'\n';
}
}
return 0;
}
/*
1
7 8 2
1 2
2 3
3 7
2 5
5 6
3 6
1 4
4 5
1 4
*/
写在最后
后面忘了。
作者@Luckyblock，转载请声明出处。