2019 ICPC 南京 网络赛
solve ： 3/10
补题 ： 5/10
https://www.jisuanke.com/contest/3004?view=challenges
A、The beautiful values of the palace
开场先开A，开了一眼这曲线不是去年蓝桥杯省赛的题吗，然后随便判了一下（大概15分钟）把值求出来了。
然后开始思考用线段树来实现nlogn，，因为 数据范围
写了一个半小时，Debug完了，队友怂恿我交一发，WA了，然后改成了 
然后发现F题过的挺多的，随便推了一下，发现是个裸的主席树？（太假了，应该先直接开F
后期演了一波说这个线段树有问题，不能这样做。然后全队跑去开B。（其实是因为我使用的方法有问题。
感觉在决定要离散化的时候正常比赛就完了啊，离散化
今天上午补了一波题，将线段树做法修正后，爆炸WA，然后看了一眼老哥代码，？？？
这个值等于数位和？不是，我不等于数位和为啥过了样例啊。原来最大的问题不是线段树，然后把第一发错误代码拉过来交了一下。居然过了，太假了
没有离散化的代码：
| 正确通过 | 2019-09-02 10:48 | 1148ms | 102728kB | c++ |
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
ll n, m, q;
ll gets(ll xx, ll yy)
{
ll x = -yy, y = -xx;
if (x >= 0)
{
if (y >= 0)
{
if (y >= x)
return 4 * y * y - y + x + 1;
else
return 4 * x * x + x - y + 1;
}
else
{
if (y >= -x)
return (2 * x + 1) * (2 * x) - x - y + 1;
else
return (1 - 2 * y) * (2 * (-y)) - x - y + 1;
}
}
else
{
if (y >= 0)
{
if (y >= -x)
return (2 * y) * (2 * y - 1) + x + y + 1;
else
return (2 * (-x)) * (2 * (-x) - 1) + x + y + 1;
}
else
{
if (y >= x + 1)
return (-1 - 2 * x) * (-1 - 2 * x) - x - 1 + y + 1;
else
return (1 - 2 * y) * (1 - 2 * y) - x - 1 + y + 1;
}
}
}
ll get(ll x, ll y)
{
return n * n - gets(x - (n + 1) / 2, y - (n + 1) / 2) + 1;
}
ll gg(ll num)
{
ll res = 0;
while (num)
{
res += num % 10;
num /= 10;
}
return res;
}
const int MAXN = 1e6 + 5;
struct node
{
int l;
int r;
ll sum;
}que[1000010 * 4];
int ql, qr;
ll val;
void up(int k)
{
que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
}
void build(int left = 1, int right = MAXN, int k = 1)
{
que[k].l = left;
que[k].r = right;
que[k].sum = 0;
if (left == right)
return;
imid;
build(lson);
build(rson);
}
void update(int left = 1, int right = MAXN, int k = 1)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].sum = que[k].sum + val;
return;
}
imid;
update(lson);
update(rson);
up(k);
}
ll query(int left = 1, int right = MAXN, int k = 1)
{
if (qr < left || right < ql)
return 0;
if (ql <= left && right <= qr)
return que[k].sum;
imid;
return query(lson) + query(rson);
}
struct note
{
ll x;
ll y;
ll num;
}a[500005];
struct qq
{
ll x1;
ll y1;
ll x2;
ll y2;
}in[100005];
int cnt;
#define Pair pair<int,int>
int main()
{
int T;
sc("%d", &T);
while (T--)
{
map<Pair, ll>mp;
sc("%d%d%d", &n, &m, &q);
cnt = 0;
for (int i = 0; i < m; i++)
{
sc("%lld%lld", &a[i].x, &a[i].y);
a[i].num = get(a[i].x, a[i].y);
a[i].num = gg(a[i].num);
}
cnt = m;
for (int i = 0; i < q; i++)
{
sc("%lld%lld%lld%lld", &in[i].x1, &in[i].y1, &in[i].x2, &in[i].y2);
a[cnt++] = note{ in[i].x1 - 1, in[i].y1 - 1, 0 };
a[cnt++] = note{ in[i].x2, in[i].y2, 0 };
a[cnt++] = note{ in[i].x1 - 1, in[i].y2, 0 };
a[cnt++] = note{ in[i].x2, in[i].y1 - 1, 0 };
}
sort(a, a + cnt, [](note q, note w) {
if (q.x == w.x)
{
if (q.y == w.y)
return q.num > w.num;
else
return q.y < w.y;
}
return q.x < w.x;
});
build();
for (int i = 0; i < cnt; i++)
{
if (a[i].num == 0)
{
ql = 1, qr = a[i].y;
ll ans = query();
mp[Pair{ a[i].x,a[i].y }] = ans;
}
else
{
ql = qr = a[i].y, val = a[i].num;
update();
}
}
for (int i = 0; i < q; i++)
{
ll ans = mp[Pair{ in[i].x2,in[i].y2 }] - mp[Pair{ in[i].x1 - 1,in[i].y2 }] - mp[Pair{ in[i].x2,in[i].y1 - 1 }] + mp[Pair{ in[i].x1 - 1,in[i].y1 - 1 }];
pr("%lld\n", ans);
}
}
} 离散化的代码：
| 正确通过 | 2019-09-02 10:44 | 1440ms | 81632kB | c++ |
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
ll n, m, q;
ll gets(ll xx, ll yy)
{
ll x = -yy, y = -xx;
if (x >= 0)
{
if (y >= 0)
{
if (y >= x)
return 4 * y * y - y + x + 1;
else
return 4 * x * x + x - y + 1;
}
else
{
if (y >= -x)
return (2 * x + 1) * (2 * x) - x - y + 1;
else
return (1 - 2 * y) * (2 * (-y)) - x - y + 1;
}
}
else
{
if (y >= 0)
{
if (y >= -x)
return (2 * y) * (2 * y - 1) + x + y + 1;
else
return (2 * (-x)) * (2 * (-x) - 1) + x + y + 1;
}
else
{
if (y >= x + 1)
return (-1 - 2 * x) * (-1 - 2 * x) - x - 1 + y + 1;
else
return (1 - 2 * y) * (1 - 2 * y) - x - 1 + y + 1;
}
}
}
ll gg(ll num)
{
ll res = 0;
while (num)
{
res += num % 10;
num /= 10;
}
return res;
}
ll get(ll x, ll y)
{
return n * n - gets(x - (n + 1) / 2, y - (n + 1) / 2) + 1;
}
struct node
{
int l;
int r;
ll sum;
}que[500010 * 4];
int ql, qr;
ll val;
void up(int k)
{
que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
}
void build(int left = 1, int right = 500005, int k = 1)
{
que[k].l = left;
que[k].r = right;
que[k].sum = 0;
if (left == right)
return;
imid;
build(lson);
build(rson);
}
void update(int left = 1, int right = 500005, int k = 1)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].sum = que[k].sum + val;
return;
}
imid;
update(lson);
update(rson);
up(k);
}
ll query(int left = 1, int right = 500005, int k = 1)
{
if (qr < left || right < ql)
return 0;
if (ql <= left && right <= qr)
return que[k].sum;
imid;
return query(lson) + query(rson);
}
struct in
{
ll x;
ll y;
ll num;
}a[500005];
struct qq
{
ll x1;
ll y1;
ll x2;
ll y2;
}qqq[100005];
ll qwe[100005][8];
int tx[500005], ty[500005];
int qqa, qqb, cnta, cntb, cnt;
void add(ll x, ll y)
{
a[cnt++] = in{ x,y,0 };
}
#define Pair pair<int,int>
int main()
{
int T;
sc("%d", &T);
while (T--)
{
map<Pair, ll>mp;
sc("%d%d%d", &n, &m, &q);
cnta = 0, cntb = 0;
cnt = 0;
for (int i = 0; i < m; i++)
{
sc("%lld%lld", &a[i].x, &a[i].y);
a[i].num = gg(get(a[i].x, a[i].y));
tx[cnta++] = a[i].x;
ty[cntb++] = a[i].y;
}
cnt = m;
for (int i = 0; i < q; i++)
{
sc("%lld%lld%lld%lld", &qqq[i].x1, &qqq[i].y1, &qqq[i].x2, &qqq[i].y2);
tx[cnta++] = qqq[i].x1 - 1;
tx[cnta++] = qqq[i].x2;
ty[cntb++] = qqq[i].y1 - 1;
ty[cntb++] = qqq[i].y2;
/*add(qqq[i].x1 - 1, qqq[i].y1 - 1);
add(qqq[i].x2, qqq[i].y2);
add(qqq[i].x1 - 1, qqq[i].y2);
add(qqq[i].x2, qqq[i].y1 - 1);
qqq[i].x1 = upper_bound(tx, tx + qqa, qqq[i].x1) - tx + 1;
qqq[i].x2 = upper_bound(tx, tx + qqa, qqq[i].x2) - tx + 1;
qqq[i].y1 = upper_bound(ty, ty + qqb, qqq[i].y1) - ty + 1;
qqq[i].y2 = upper_bound(ty, ty + qqb, qqq[i].y2) - ty + 1;*/
}
//a[cnt++] = in{ x,y,0 };
sort(tx, tx + cnta);
sort(ty, ty + cntb);
qqa = unique(tx, tx + cnta) - tx;
qqb = unique(ty, ty + cntb) - ty;
for (int i = 0; i < m; i++)
{
a[i].x = lower_bound(tx, tx + qqa, a[i].x) - tx + 1;
a[i].y = lower_bound(ty, ty + qqb, a[i].y) - ty + 1;
}
for (int i = 0; i < q; i++)
{
int q1 = lower_bound(tx, tx + qqa, qqq[i].x1 - 1) - tx + 1;
int w1 = lower_bound(ty, ty + qqb, qqq[i].y1 - 1) - ty + 1;
qwe[i][0] = q1;
qwe[i][1] = w1;
a[cnt++] = in{ q1,w1,0 };
q1 = lower_bound(tx, tx + qqa, qqq[i].x2) - tx + 1;
w1 = lower_bound(ty, ty + qqb, qqq[i].y1 - 1) - ty + 1;
qwe[i][2] = q1;
qwe[i][3] = w1;
a[cnt++] = in{ q1,w1,0 };
q1 = lower_bound(tx, tx + qqa, qqq[i].x1 - 1) - tx + 1;
w1 = lower_bound(ty, ty + qqb, qqq[i].y2) - ty + 1;
qwe[i][4] = q1;
qwe[i][5] = w1;
a[cnt++] = in{ q1,w1,0 };
q1 = lower_bound(tx, tx + qqa, qqq[i].x2) - tx + 1;
w1 = lower_bound(ty, ty + qqb, qqq[i].y2) - ty + 1;
qwe[i][6] = q1;
qwe[i][7] = w1;
a[cnt++] = in{ q1,w1,0 };
}
sort(a, a + cnt, [](in q, in w) {
if (q.x == w.x)
{
if (q.y == w.y)
return q.num > w.num;
else
return q.y < w.y;
}
return q.x < w.x;
});
build();
for (int i = 0; i < cnt; i++)
{
if (a[i].num == 0)
{
ql = 1, qr = a[i].y;
ll ans = query();
mp[Pair{ a[i].x,a[i].y }] = ans;
}
else
{
ql = qr = a[i].y, val = a[i].num;
update();
}
}
for (int i = 0; i < q; i++)
{
ll ans = mp[Pair{ qwe[i][6],qwe[i][7] }] - mp[Pair{ qwe[i][2],qwe[i][3] }] - mp[Pair{ qwe[i][4],qwe[i][5] }] + mp[Pair{ qwe[i][0],qwe[i][1] }];
pr("%lld\n", ans);
}
}
} B、super_log
求 
欧拉降幂
欧拉定理：
降幂公式：
其中，第一个公式要求 a 和 mod 互质，第二第三个公式不要求 a mod 互质。
所以只要先搞最高次幂，递归就可以了，赛时快速幂没写欧拉降幂。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll power(ll a, ll b, ll mod)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a;
if (res >= mod)
res = res % mod + mod;
}
a = a * a;
if (a >= mod)
a = a % mod + mod;
b >>= 1;
}
return res;
}
ll phi(ll n)
{
ll res = n;
for (ll i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
res = res - res / i;
while (n % i == 0)
n /= i;
}
}
if (n > 1)
res = res - res / n;
return res;
}
ll dfs(ll n, ll m, ll cnt)
{
if (m == 1)
{
if (n == 0)
return 0;
else
return 1;
}
if (cnt == 1)
{
if (n >= m)
return n % m + m;
return n;
}
return power(n, dfs(n, phi(m), cnt - 1), m);
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
ll a, b, mod;
sc("%lld%lld%lld", &a, &b, &mod);
if (b == 0)
{
pr("%lld\n", 1 % mod);
continue;
}
else if (b == 1)
{
pr("%lld\n", a % mod);
continue;
}
else
{
b--;
ll ans = dfs(a, phi(mod), b);
ans = power(a, ans, mod);
pr("%lld\n", ans % mod);
}
}
} F、Greedy Sequence
排个序，从小遍历到大，然后求一下这个数字在当前区间的个数k，然后求区间k-1小的值，然后转移
int id[MAXN];
int ans[MAXN];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
t[i] = a[i];
id[a[i]] = i;
ans[i] = 0;
}
sort(t + 1, t + 1 + n);
int qq = unique(t + 1, t + 1 + n) - t - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(t + 1, t + qq + 1, a[i]) - t;
init();
for (int i = 1; i <= n; i++)
{
root[i] = root[i - 1];
build(a[i], root[i], 1, n);
}
int ql, qr, k;
for (int i = 1; i <= n; i++)
{
ql = max(id[i] - m, 1);
qr = min(id[i] + m, n);
int tot = querycnt(root[ql - 1], root[qr], 1, i, 1, n);
k = tot - 1;
if (k == 0)
{
ans[i] = 1;
}
else
{
int pos = query(root[ql - 1], root[qr], k, 1, n);
ans[i] = ans[pos] + 1;
}
}
for (int i = 1; i <= n; i++)
pr("%d%c", ans[i], i == n ? '\n' : ' ');
}
} H、Holy Grail
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
#define M 20005
using namespace std;
typedef long long ll;
const ll INF = 1e12;
ll n,m,t;
ll v[M],w[M],nextt[M];
ll d[N],cnt[N],first[N];
bool vis[N];
void add(ll x,ll y,ll z)
{
t++;
nextt[t]=first[x];
first[x]=t;
v[t]=y;
w[t]=z;
}
bool SPFA(ll s)
{
ll x,y,i,j;
queue<ll>q;
for(int i=0;i<=n;++i) d[i]=INF,vis[i]=false;
// memset(d,127,sizeof(d));
// memset(vis,false,sizeof(vis));
while(!q.empty()) q.pop();
d[s]=0;
cnt[s]=1;
q.push(s);
vis[s]=true;
while(!q.empty())
{
x=q.front();
q.pop();
vis[x]=false;
for(i=first[x];i;i=nextt[i])
{
y=v[i];
if(d[y]>d[x]+w[i])
{
d[y]=d[x]+w[i];
cnt[y]=cnt[x]+1;
if(cnt[y]>n)
return false;
if(!vis[y])
{
q.push(y);
vis[y]=true;
}
}
}
}
return true;
}
int main()
{
ll T;
scanf("%lld",&T);
while(T--){
ll x,y,z,i;
scanf("%lld%lld",&n,&m);
for(int i=0;i<=n;++i) first[i]=0;
t=0;
for(i=1;i<=m;++i)
{
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
}
for(int i=1;i<=6;++i){
ll a,b;
scanf("%lld%lld",&a,&b);
ll c = -INF;
add(a,b,c);
ll l = -2e12,r = 1e12;
ll ans;
while(l+1<r){
ll mid = (l+r)>>1;
w[t]=mid;
if(!SPFA(b)) l=mid;
else r=mid;
}
w[t]=l;
if(!SPFA(b))
ans=r;
else ans=l;
printf("%lld\n",ans);
w[t]=ans;
}
}
return 0;
}
投递淘天集团等公司10个岗位 >