The Preliminary Contest for ICPC Asia Nanjing 2019
A The beautiful values of the palace
题目链接
题意：在一个n*n的螺旋矩阵，给你m个坐标(x,y)代表此下标是存在数的。再给q个询问，询问左下角(x1,y1)和右上角(x2,y2)为矩阵中存在的数的数位和。
思路：对于一个坐标(x,y)在螺旋矩阵中的数值，可以通过近似O(1)的计算得出。计算矩阵中有多少个存在的值，我们通过对于m个坐标进行排序，建立主席树。x坐标存在重复所以需要lower_bound(),upper_bound()二分。
#include <bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
struct node{
int l,r;
ll cnt;
node(){
l=r=cnt=0;
}
}T[maxn*22];
struct point{
int x,y;
}p[maxn];
bool cmp(point a,point b){
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int get_beauty(ll n, ll x, ll y){
ll top = n - y, bottom = y - 1, lft = x - 1, rht = n - x;
ll dis = min(min(top,bottom),min(lft,rht));
ll has = n * n - ((n - dis * 2) * (n - dis * 2));
ll edge = n - 2 * dis - 1;
if(x == n - dis){
has += top - dis + 1;
}
else if(y == dis + 1){
has += edge + rht - dis + 1;
}
else if(x == dis + 1){
has += 2 * edge + bottom - dis + 1;
}
else{
has += 3 * edge + lft - dis + 1;
}
int wei = 0;
while(has){
wei += has % 10;
has /= 10;
}
return wei;
}
int rt[maxn];
int xCopy[maxn];
int tot=0;
int n,m,q;
void update(int &x,int y,int l,int r,int pos,int val){
T[++tot]=T[y];
T[tot].cnt+=val;
x=tot;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)
update(T[x].l,T[y].l,l,mid,pos,val);
else
update(T[x].r,T[y].r,mid+1,r,pos,val);
}
int ans=0;
void query(int x,int y,int l,int r,int L,int R){
if (L <= l && r <= R) {
ans += T[y].cnt - T[x].cnt;
return;
}
int mid = l + r >> 1;
if (L <= mid)query(T[x].l, T[y].l, l, mid, L, R);
if (R > mid)query(T[x].r, T[y].r, mid + 1, r, L, R);
}
void init(){
tot=0;
}
void input(){
scanf("%d%d%d",&n,&m,&q);
int i;
for(i=1;i<=m;i++)
scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+1+m,cmp);
for(i=1;i<=m;i++){
update(rt[i],rt[i-1],1,n,p[i].y,get_beauty(1ll*n,1ll*p[i].x,1ll*p[i].y));
xCopy[i]=p[i].x;
}
int x1,y1,x2,y2;
for(i=1;i<=q;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int pos1=lower_bound(xCopy+1,xCopy+1+m,x1)-xCopy;
int pos2=upper_bound(xCopy+1,xCopy+1+m,x2)-xCopy-1;
// cout<<pos1<<' '<<pos2<<endl;
ans=0;
query(rt[pos1-1],rt[pos2],1,n,y1,y2);
printf("%d\n",ans);
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
init();
input();
// solve();
}
} D Robots
题目链接
题意：问一个机器人从图中1到n所需要的燃油值期望为多少？每次耗费的燃油值，是当前已经历的天数值。
思路：拓扑求出天数的期望值，再拓扑求出耗油的期望值。
其中t[u]是天数期望，f[u]是耗油期望
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int t;
int n,m;
vector <int>G[maxn];
vector <int>g[maxn];
int indeg[maxn];
int indegCopy[maxn];
double day[maxn];
double ans[maxn];
void topo(){
int i;
queue <int>q;
for(i=1;i<=n;i++)
if(!indeg[i]){
day[i]=0;
q.push(i);
}
while(!q.empty()){
int f=q.front();
q.pop();
for(int i=0;i<G[f].size();i++){
indeg[G[f][i]]--;
if(!indeg[G[f][i]])
{
q.push(G[f][i]);
for(int j=0;j<g[G[f][i]].size();j++)
day[G[f][i]]+=day[g[G[f][i]][j]];
day[G[f][i]]+=(g[G[f][i]].size()+1);
day[G[f][i]]/=g[G[f][i]].size();
}
}
}
}
void topo2(){
int i;
queue <int>q;
for(i=1;i<=n;i++)
if(!indeg[i]){
ans[i]=0;
q.push(i);
}
while(!q.empty()){
int f=q.front();
q.pop();
for(int i=0;i<G[f].size();i++){
indeg[G[f][i]]--;
if(!indeg[G[f][i]])
{
q.push(G[f][i]);
for(int j=0;j<g[G[f][i]].size();j++)
ans[G[f][i]]+=ans[g[G[f][i]][j]];
ans[G[f][i]]+=(g[G[f][i]].size()+1)*day[G[f][i]];
ans[G[f][i]]/=g[G[f][i]].size();
}
}
}
}
void input(){
scanf("%d%d",&n,&m);
int i,u,v;
for(i=1;i<=n;i++){
G[i].clear();
g[i].clear();
}
memset(day,0,sizeof day);
memset(ans,0,sizeof ans);
memset(indeg,0,sizeof indeg);
memset(indegCopy,0,sizeof indegCopy);
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
G[v].push_back(u);
g[u].push_back(v);
indeg[u]++;
indegCopy[u]++;
}
}
void solve(){
topo();
// for(int i=1;i<=n;i++)
// cout<<day[i]<<endl;
for(int i=1;i<=n;i++)
indeg[i]=indegCopy[i];
topo2();
printf("%.2lf\n",ans[1]);
}
int main(){
scanf("%d",&t);
while(t--){
input();
solve();
}
} F Greedy Sequence
题目链接
题意：有n个序列S1、S2....Sn ，每个序列定义：1、Si[1]=i。2、每个序列Si都是非递增序列 3、序列Si中的上一个值和下一个值在给定排列a中的距离差需要小于等于k。4、满足Si字典序大于Si-1 5、未确定的值用0代替。
要求寻找每个序列中非零值个数。
思路：滑动窗口+multiset二分获得元素的下一个元素，记忆化O（n）记录答案
#include <bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
int n,k;
int a[maxn];
int dis[maxn];
int ans[maxn];
multiset <int>st;
multiset <int>::iterator it;
void init(){
st.clear();
int i;
for(i=1;i<=k;i++)
st.insert(a[i]);
for(i=1;i<=n;i++){
st.erase(a[i]);
if(i>1)
st.insert(a[i-1]);
if(i>k+1)
st.erase(a[i-k-1]);
if(i+k<=n)
st.insert(a[i+k]);
it=st.lower_bound(a[i]);
if(it!=st.begin())
{
it--;
dis[a[i]]=*it;
}else
dis[a[i]]=0;
}
}
void input(){
scanf("%d%d",&n,&k);
int i;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
init();
// for(i=1;i<=n;i++){
// cout<<a[i]<<" "<<dis[a[i]]<<endl;
// }
for(i=1;i<=n;i++){
if(dis[i]!=0)
ans[i]=ans[dis[i]]+1;
else
ans[i]=1;
}
for(i=1;i<=n;i++)
printf("%d%c",ans[i],i==n?'\n':' ');
}
int main(){
int t;
scanf("%d",&t);
while(t--){
input();
// solve();
}
} H Holy Grail
题目链接
题意：n个点m条边，存在负边但不存在负环的图。给出6个查询，询问点u和v，求v到u增加边（可以为负），使权值最小。
思路：输出v到u的最短路的相反数，并将u到v，权值为刚才求出的答案这条边加入到图中
#include <bits/stdc++.h>
#define maxn 305
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct edge{
int to,cost;
};
typedef pair<int,int>P;
vector <edge> G[maxn];
int dis[maxn];
void dij(int a)
{
priority_queue<P,vector<P>,greater<P> >q;
memset(dis,0x3f,sizeof(dis));
dis[a]=0;
q.push(P(0,a));
while(!q.empty())
{
P temp=q.top();
q.pop();
int v=temp.second;
if(dis[v]<temp.first)continue;
for(int i=0;i<G[v].size();i++)
{
edge e=G[v][i];
if(dis[e.to]>dis[v]+e.cost)
{
dis[e.to]=dis[v]+e.cost;
q.push(P(dis[e.to],e.to));
}
}
}
}
void input(){
scanf("%d%d",&n,&m);
int i;
for(i=0;i<n;i++)
G[i].clear();
int u,v,w;
for(i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
G[u].push_back((edge){v,w});
}
int s,t;
int q=6;
while(q--){
scanf("%d%d",&s,&t);
dij(t);
printf("%d\n",-dis[s]);
G[s].push_back((edge){t,-dis[s]});
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
input();
// solve();
}
}
京公网安备 11010502036488号