2019ICPC南京网络赛

A.00:40:35solvedbyhl很显然需要一种方法O(1)定位x,y上的数字，利用矩阵的规律可以找到然后就是一个子矩阵和问题，小范围可以直接二维前缀和，大范围就是一个二位偏

A. 00:40:35 solved by hl

很显然需要一种方法O(1)定位x,y上的数字，利用矩阵的规律可以找到

然后就是一个子矩阵和问题，小范围可以直接二维前缀和，大范围就是一个二位偏序问题，

将一个询问拆成4个询问，树状数组解决即可

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair#define PIL pair#define PLL pair#define pb push_back#define fi first#define se second typedef vector VI;int read(){int x = 0,f = 1;char c = getchar();while (c‘9‘){if (c == ‘-‘) f = -1;c = getchar();}while (c >= ‘0‘c = getchar();}return x*f;}const double PI = acos(-1.0);const double eps = 1e-9;const int maxn = 1e6 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,Q;LL pre[maxn];void init(){ pre[0] = 0; for(int sum = N,i = 1; sum > 0; i ++,sum -= 2){ pre[i] = pre[i - 1] + sum + sum + sum + sum - 4; }}inline int min(int a,int b,int c,int d){ return min(min(min(a,b),c),d);}inline LL id(int x,int y){ int q = min(x,y,N - x + 1,N - y + 1); LL ans = pre[q - 1] + 1; int sx = N - q + 1,sy = N - q + 1; if(sx == x) return ans + sy - y; ans += sy - q; sy = q; if(sy == y) return ans + sx - x; ans += sx - q; sx = q; if(sx == x) return ans + y - sy; ans += (N - q + 1) - sy; sy = N - q + 1; return ans + x - sx;}inline LL val(int x,int y){ LL sum = id(x,y); LL ans = 0; while(sum){ ans += sum % 10; sum /= 10; } return ans;}struct Good{ int x,y; LL ans;}g[maxn];struct Query{ int x,y,id,flag; Query(int x = 0,int y = 0,int id = 0,int flag = 0):x(x),y(y),id(id),flag(flag){}}query[maxn];LL fans[maxn];bool cmp(Good a,Good b){ return a.x < b.x;}LL tree[maxn];void add(int u,int v){ for(;u <= N; u += u }LL getsum(int u){ LL ans = 0; for(;u > 0; u -= u return ans;}bool cmp2(Query a,Query b){ return a.x < b.x;}int main(){ int T = read(); while(T--){ Mem(tree,0); Sca3(N,M,Q);init(); for(int i = 1; i <= Q; i ++) fans[i] = 0; for(int i = 1; i <= M; i ++){ g[i].x = read(),g[i].y = read(); g[i].ans = val(g[i].x,g[i].y); } int cnt = 0; for(int i = 1; i <= Q; i ++){ int x1 = read(),y1 = read(),x2 = read(),y2 = read(); query[++cnt] = Query(x1 - 1,y1 - 1,i,1); query[++cnt] = Query(x2,y1 - 1,i,-1); query[++cnt] = Query(x1 - 1,y2,i,-1); query[++cnt] = Query(x2,y2,i,1); } sort(g + 1,g + 1 + M,cmp); sort(query + 1,query + 1 + cnt,cmp2); int s1 = 1,s2 = 1; for(int i = 0; i <= N ; i ++){ while(s1 <= M s1++; } while(s2 <= cnt s2++; } } for(int i = 1; i <= Q; i ++) Prl(fans[i]); } return 0;}A

B.1:42:29(-1) solved by gbs

队友说 是裸的指数循环节

#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;int a,b,m;LL eular(LL n){ LL ans = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { ans -= ans / i; while (n % i == 0) n /= i; } } if (n != 1) ans -=ans / n; return ans;}const LL mod = 1e9 + 7; //int quick_mi(LL a, LL k,LL mod){ if (k == 0) return 1; if (a<=1) return a; bool if_over = false; LL k1 = 1; for (int i=0; i= mod) { if_over = true; break; } } LL ans = 1; while (k) { if (k ans %= mod; } a *= a; a %= mod; k >>= 1; } if (if_over) { ans += mod; } return ans;}LL dfs(int a,int b,LL mod){ if (b == 0) return 1; if (b == 1) return a; if (mod == 1) return 1; LL h1=quick_mi(a,dfs(a,b-1,eular(mod)),mod); //cout<>t; while(t--) { cin >>a>>b>>m; int h1 = dfs(a,b,m); cout<

D.00:44:59 solved by zcz

#include#include#include#includeusing namespace std;double p1[100005],p2[100005];int n,m;vector e[100005];double getp2(int u){ if(p2[u]>=0) return p2[u]; int l=e[u].size(); double rec=0; for(int i=0;i=0) return p1[u]; int l=e[u].size(); double rec=0; for(int i=0;i>T; while(T--) { cin>>n>>m; for(int i=1;i<=n;i++) { p1[i]=-1,p2[i]=-1; e[i].clear(); } p2[n]=1; p1[n]=0; while(m--) { int u,v; scanf("%d%d", e[u].push_back(v); } getp2(1); getp1(1); printf("%.2lf\n",p1[1]); } return 0;}D

F.1:30:28 solved by zcz and hl

线段树维护区间最大值的下标，按照数的大小从小到大询问然后修改

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair#define PIL pair#define PLL pair#define pb push_back#define fi first#define se second typedef vector VI;int read(){int x = 0,f = 1;char c = getchar();while (c‘9‘){if (c == ‘-‘) f = -1;c = getchar();}while (c >= ‘0‘c = getchar();}return x*f;}const double PI = acos(-1.0);const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;int a[maxn],id[maxn];int ans[maxn];struct node{ int pos,val; node(int pos = 0,int val = 0):pos(pos),val(val){} friend node operator + (node a,node b){ if(a.val > 1; Build(t <<1,l,m); Build(t <<1 | 1,m + 1,r); Pushup(t);}node query(int t,int l,int r){ if(l <= tree[t].l } int m = tree[t].l + tree[t].r >> 1; if(r <= m) return query(t <<1,l,r); else if(l > m) return query(t <<1 | 1,l,r); else{ return query(t <<1,l,m) + query(t <<1 | 1,m + 1,r); }}void update(int t,int pos){ if(tree[t].l == tree[t].r){ tree[t].ans.val = a[pos]; return; } int m = (tree[t].l + tree[t].r) >> 1; if(pos <= m) update(t <<1,pos); else update(t <<1 | 1,pos); Pushup(t);}int main(){ int T = read(); while(T--){ Sca2(N,K); for(int i = 1; i <= N; i ++) ans[i] = 0; for(int i = 1; i <= N ; i ++) Sca(a[i]),id[a[i]] = i; Build(1,1,N); for(int i = 1; i <= N ; i ++){ int l = max(1,id[i] - K),r = min(N,id[i] + K); node t = query(1,l,r); ans[i] = ans[t.val] + 1; update(1,id[i]); } for(int i = 1; i <= N; i ++){ printf("%d",ans[i]); if(i != N) printf(" "); } puts(""); } return 0;}F

G.4:35:30(-7) solved by zcz

一个很麻烦的线性规划

#include#include#include#includeusing namespace std;long long f(long long a,long long b,long long c){ if(a=a+b) return (a+1)*(b+1); if(c<=b) return (c+1)*(c+2)/2; if(b>T; while(T--) { long long l1,l2,l3,l4,r1,r2,r3,r4; cin>>l1>>r1>>l2>>r2>>l3>>r3>>l4>>r4; if(r1

H.1:06:48(-1) solved by hl

没有负环的条件是没有一条来的路和加的边加起来为负，所以每次加的边为反向最短路

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair#define PIL pair#define PLL pair#define pb push_back#define fi first#define se second typedef vector VI;int read(){int x = 0,f = 1;char c = getchar();while (c‘9‘){if (c == ‘-‘) f = -1;c = getchar();}while (c >= ‘0‘c = getchar();}return x*f;}const double PI = acos(-1.0);const double eps = 1e-9;const int maxn = 310;const int maxm = 710;const LL INF = 1e18;const int mod = 1e9 + 7; int N,M,K;struct Edge{ int to,next; LL dis;}edge[maxm * 2];int head[maxn],tot;void init(){ for(int i = 0 ; i <= N ; i ++) head[i] = -1; tot = 0;}void add(int u,int v,LL w){ edge[tot].to = v; edge[tot].next = head[u]; edge[tot].dis = w; head[u] = tot++;}LL dis[1005],vis[1005];struct node{ int pos; LL val; node(int pos,LL val):pos(pos),val(val){} friend bool operator < (node a,node b){ return a.val > b.val; }};LL Dijkstra(int s,int t){ for(int i = 0; i <= N ; i ++) dis[i] = INF; dis[s] = 0; priority_queueQ; Q.push(node(s,0)); while(!Q.empty()){ node u = Q.top(); Q.pop(); if(u.val > dis[u.pos]) continue; for(int i = head[u.pos]; ~i; i = edge[i].next){ int v = edge[i].to; if(dis[v] > edge[i].dis + u.val){ dis[v] = edge[i].dis + u.val; Q.push(node(v,dis[v])); } } } return dis[t];}int main(){ int T = read(); while(T--){ Sca2(N,M); init(); for(int i = 1; i <= M ; i ++){ int u = read(),v = read(); LL w = read(); add(u,v,w); } for(int i = 1; i <= 6; i ++){ int u = read(),v = read(); //S = u,T = v; LL ans = -Dijkstra(v,u); add(u,v,ans); Prl(ans); } } return 0;}H

I.2:40:04(-5) solved by gbs

已经多次证实两个人敲同一道题的后果就是罚时++

隐约听到了队友说的类似于玄学，暴力之类的做法

#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;int an[1123456];int ans[123456];int main(){ int N; int y; while(cin >>N>>y) { for (int i=0; i=1; j--) { if (nowi == 0) { ans[j] = an[N-1]+j; continue; } now_ans = max(an[N-1]+j,an[nowi-1]+y); while(an[nowi-1] + j<=an[nowi]) { nowi--; if (nowi == 0) { now_ans = an[N-1]+j; break; } now_ans = max(an[N-1]+j,an[nowi-1]+y); } ans[j] = now_ans; } } for (int j=1; j<=y; j++) { if (j!=1) printf(" "); printf("%d",ans[j]); } printf("\n"); }#ifdef VSCode system("pause");#endif return 0;}I