2020ICPC江西省程序设计竞赛赛后总结
第一次icpc江西省赛差点金，逃离大气层牛逼
开场rk3，打完只有rk15 QAQ（开题都没开出来，挺难受的），最后只有银3，就差一点就拿到金了。
不过现在才大二，后面还有挺多机会，12月上海冲冲冲
以下是看了的题的代码：
A - A Simple Math Problem
虽然没想到正解，但我们这个代码可以跑8e4，最后优化一下常数应该也能过，可惜没有搞出来
#include
using namespace std;
#define ll long long
const int maxn = 1e5 +10;
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
ll mod = 998244353;
int v[maxn],p[maxn],tot=0;
void Euler(int n)
{
v[1]=1;
for(int i=2;i<=n;i++){
if(v[i]==0){v[i]=i;p[++tot]=i;}
for(int j=1;j<=tot;j++)
{
if(p[j]>v[i]||p[j]>n/i)break;
v[i*p[j]]=p[j];
}
}
}
int vis[maxn];
int main()
{
fastio;
int n;
cin>>n;
Euler(n+1);
ll ans = n;
int flag=1;
for(int i=2;i<=n;++i)
{
ll cnt=n-i+1,tmp=i;
if(v[i]==i)
cnt-=n/i;
else
{
while(tmp > 1)
{
ll P=v[tmp];
for(int j=i/v[tmp]*v[tmp];j<=n;j+=P)
{
(vis[j]!=i)?
cnt--,vis[j]=i:0;
}
while(tmp>1&&tmp%P==0)
{
tmp/=P;
}
}
}
ll f=0;
int x=i;
while(x)
{
f+=x%10;
x/=10;
}
ans+=cnt*f;
}
cout< 其实一开场就看了10分钟A，我们都不太会数学，就跑去跟榜了
正解：和上面代码的公式一样，只是求cnt需要用容斥去优化求n以内与x互质的数的个数（其实就是n-n以内与x不互质的数），即求\(cnt = n - solve(x,n) - phi(x)\)
#include
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
ll mod = 998244353;
int v[maxn], p[maxn], phi[maxn], tot;
void Euler_sieve(int n)
{
tot = 0;
for (int i = 2; i <= n; i++) {
if (v[i] == 0) { v[i] = i, p[++tot] = i, phi[i] = i - 1; }
for (int j = 1; j <= tot; j++)
{
if (p[j] > v[i] || p[j] > n / i)break;
v[i * p[j]] = p[j];
phi[i * p[j]] = phi[i] * (i % p[j] ? p[j] - 1 : p[j]);
}
}
}
int f(int x)
{
int res = 0;
while (x)
{
res += x % 10;
x /= 10;
}
return res;
}
int solve(int x,int n)//筛n以内与x不互质的数的个数
{
vectortmp;
while (x > 1)
{
int P = v[x];
tmp.push_back(P);
while (x % P == 0)
x /= P;
}
int res = 0;
int num = tmp.size();
for (int i = 1; i < (1 << num); i++)
{
bool flag = 0;
int now = 1;
for (int j = 0; j < num; j++)
{
if ((1 << j) & i)
{
flag ^= 1;
now *= tmp[j];
}
}
if (!flag)
res -= n / now;
else
res += n / now;
}
return res;
}
int main()
{
fastio;
int n;
cin >> n;
Euler_sieve(n + 1);
ll ans = n;
for (int i = 2; i <= n; ++i)
{
ll cnt = n - solve(i, n) - phi[i];
ans += cnt * f(i);
}
cout << ans;
return 0;
}
看见前面的队都用反演过的，谁来教教我数学QAQ
B-Apple
签到，直接求和公式
#include
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
int main()
{
int t;
cin>>t;
while(t--)
{
ll sum,n;
cin>>sum>>n;
if((1+n)*n/2>sum)
cout<<"impossible"< C读错题了，和队友搞了2个多小时无了，太致命了
E-Color Sequence
zbj????，光速想出位运算做法，听了一遍思路讨论了一下发现是把之前出现过的状态的次数累加前缀和，光速切掉
#include
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
const int maxn= 1e6 + 10;
ll cnt[1<<21];
ll py[21];
int main()
{
fastio;
int n;
cin>>n;
for(int i=0;i<=20;i++)
py[i]=(1<>x;
zt^=py[x];
ans+=cnt[zt];
cnt[zt]++;
}
cout< G-Mathematical Practice
榜歪了，没人做，我们直接拿一血，还是队友牛逼
#include
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
ll mod = 998244353;
ll qpow(ll x, ll y)
{
ll res = 1;
x %= mod;
while (y)
{
if (y & 1)res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res%mod;
}
int main()
{
ll n, m;
cin >> n >> m;
cout << qpow(m + 1, n);
return 0;
}
H-Sequence
打的时候居然没有看这个题，没有任何难度的线段树+二分，赛后15分钟写完，我是sb
#include
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define Ls t[p<<1]
#define Rs t[p<<1|1]
using namespace std;
double pi = acos(-1);
const double eps = 1e-6;
const int maxn = 1e5 + 10;
const int inf = 1e11;
int a[maxn];
struct tree {
int l, r;
int MIN;
}t[maxn << 2];
void build(int l, int r, int p)
{
t[p].l = l, t[p].r = r;
if (l == r)
{
t[p].MIN = a[l];
return;
}
int mid = l + r >> 1;
build(l, mid, p << 1);
build(mid + 1, r, p << 1 | 1);
t[p].MIN = min(Ls.MIN, Rs.MIN);
}
void change(int to, int x, int p)
{
int l = t[p].l, r = t[p].r;
if (l == r)
{
t[p].MIN = x;
return;
}
int mid = l + r >> 1;
if (to <= mid)
change(to, x, p << 1);
else change(to, x, p << 1 | 1);
t[p].MIN = min(Ls.MIN, Rs.MIN);
}
int query(int x, int y, int p)
{
int l = t[p].l, r = t[p].r;
//cout << l << " " << r << endl;
if (x <= l && r <= y)
return t[p].MIN;
int mid = l + r >> 1;
if (x > mid)
return query(x, y, p << 1 | 1);
else if (y <= mid)
return query(x, y, p << 1);
else
return min(query(x, y, p << 1), query(x, y, p << 1 | 1));
}
int main()
{
fastio;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
build(1, n, 1);
while (m--)
{
int o;
cin >> o;
if (o == 1)
{
int x, y;
cin >> x >> y;
a[x] = y;
change(x, y, 1);
}
else
{
int x;
cin >> x;
ll L, R;
int l = 1, r = x;
while (l < r)
{
int mid = l + r >> 1;
if (query(mid, x, 1) == a[x])
r = mid;
else l = mid + 1;
}
L = x - l + 1;
l = x, r = n;
while (l <= r)
{
int mid = l + r >> 1;
//cout << l << " " << r << " " << query(x, mid, 1) << endl;
if (query(x, mid, 1) == a[x])
{
R = mid;
l = mid + 1;
}
else r = mid -1;
}
R = R - x + 1;
//cout << L << " " << R << " ";
cout << L * R << endl;
}
}
return 0;
}
I-Simple Math Problem
没看题
#include
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
ll n,x,y;
int main()
{
cin>>n>>y>>x;
if(x+y J-Split Game
SG函数，少写了两行导致wa到结束，赛后5分钟过题.jpg。
不能从能写出1*1的状态转移
错误的跑法
int sg(int x, int y)
{
if (f[x][y] != -1)return f[x][y];
sets;
for (int i = 1; i < x; i++)
s.insert(sg(x - i, y) ^ sg(i, y));
for (int i = 1; i < y; i++)
s.insert(sg(x, y - i) ^ sg(x, i));
for (int i = 0;; i++)
if (s.count(i) == 0)
{
f[x][y] = i;
break;
}
return f[x][y];
}
正确的跑法
int sg(int x, int y)
{
if (f[x][y] != -1)return f[x][y];
sets;
for (int i = 1; i < x; i++)
{
if(i==1&&y==1||i==x-1&&y==1)continue;
s.insert(sg(x - i, y) ^ sg(i, y));
}
for (int i = 1; i <= y-1; i++)
{
if(i==1&&x==1||i==y-1&&x==1)continue;
s.insert(sg(x, y - i) ^ sg(x, i));
}
for (int i = 0;; i++)
if (s.count(i) == 0)
{
f[x][y] = i;
break;
}
return f[x][y];
}
K-Travel Expense
flord+二分，看题1分钟思路秒切，不过二分写炸了调了蛮久的（手残哭了）
#include
using namespace std;
#define ll unsigned long long
const int maxn = 1e5 +10;
const ll inf = 1e18;
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
ll qpow(ll x, ll y)
{
ll res = 1;
while (y)
{
if (y & 1)res = res * x;
x = x * x;
y >>= 1;
}
return res;
}
ll d[110][110];
ll S,T,lim;
int main()
{
fastio;
ll n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=inf;
while(m--)
{
ll x,y;
cin>>x>>y;
d[x][y]=d[y][x]=1;
}
for(int i=1;i<=n;i++)d[i][i]=0;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k] + d[k][j]);
int t;
cin>>t;
while(t--)
{
cin>>S>>T>>lim;
ll l=0, r = 1e9 , ans=0;
while(l<=r)
{
ll mid=l+r>>1;
ll cost = 0;
if(mid == 1)
cost = d[S][T];
else if(mid == 0)
cost = 0;
else
cost = (mid*(qpow(mid,d[S][T])-1))/(mid-1);
//cout< lim)
r=mid-1;
else
{
ans = mid;
l=mid+1;
}
}
cout< 还是得多去刷题，攻坚能力有待加强