ACM-ICPC 2018 南京赛区网络预赛
总结 与ldq队差距 4题
A 水题 输出 n-1
B：发现了一篇很好的博客，讲得很好
链接
类似题 ：
51nod 1291 Farmer
EOJ 3514. 五彩地砖
Wannafly挑战赛12 D
。。。。。。
my_code
#include<bits/stdc++.h>
using namespace std;
const int N = (1<<20)+5;
const long long inf =1e18;
typedef long long ll;
struct node
{
ll a,b;
int pre;
} p[N];
ll dp[N];
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
scanf("%lld%lld",&p[i].a,&p[i].b);
int vc;
scanf("%d",&vc);
while(vc--)
{
int y;
scanf("%d",&y);
p[i].pre=p[i].pre|(1<<(y-1));
}
}
int nn = 1<<n;
for(int i=0; i<nn; i++)dp[i] = -inf;
dp[0]= 0;
ll ans = 0;
for(int i=0; i<nn; i++)
{
if(dp[i]==-inf)continue;
ll t = 1;
for(int j=1; j<=n; j++)
{
if(i&(1<<(j-1)))t++;
}
for(int j=1; j<=n; j++)
{
if(i&(1<<(j-1)))continue;
if(p[j].pre==0||(p[j].pre&i)>=p[j].pre)
{
int nxt= i|(1<<(j-1));
dp[nxt] = max(dp[nxt],p[j].a*t+p[j].b+dp[i]);
ans= max(ans,dp[nxt]);
}
}
}
cout<<ans<<endl;
return 0;
}
I 裸的回文树 ，最近一直在刷这个专题，可惜了 前期题卡到最后
注意N = 10，只有10个字符，只开一个回文树就可以。
马拉车+hash做法
使劲疯大佬改的原题代码
https://www.cnblogs.com/hua-dong/p/7714475.html
https://paste.ubuntu.com/p/g7MMNt87KJ/
my_code:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int MAXN = 2000008 ;
ll Pow[MAXN];
ll dp[MAXN];
char a[2000008];
const int N = 11 ;
long long ans;
struct Palindromic_Tree {
int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
long long cnt[MAXN];
int len[MAXN] ;//len[i]表示节点i表示的回文串的长度
int S[MAXN] ;//存放添加的字符
int last ;//指向上一个字符所在的节点，方便下一次add
int n ;//字符数组指针
int p ;//节点指针
int length[MAXN] ;
int newnode ( int l ) {//新建节点
for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
cnt[p] = 0 ;
// num[p] = 0 ;
len[p] = l ;
return p ++ ;
}
void init () {//初始化
p = 0 ;
newnode ( 0 ) ;
newnode ( -1 ) ;
last = 0 ;
n = 0 ;
S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
fail[0] = 1 ;
}
int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
return x ;
}
void add ( ll c ) {
c -= '0' ;
S[++ n] = c ;
int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
int now = newnode ( len[cur] + 2 ) ;//新建节点
fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
if(cur==1)
{
length[now] = 1;
dp[now] =c;
}
else if(cur==0)
{
length[now] = 2;
dp[now] = c*10+c;
}
else
{
length[now] = length[cur]+2;
dp[now] = (dp[cur]*10%mod+c*Pow[length[cur]+2]%mod+c)%mod;
}
ans+=dp[now];
ans%=mod;
next[cur][c] = now ;
// num[now] = num[fail[now]] + 1 ;
}
last = next[cur][c] ;
cnt[last] ++ ;
}
} ;
Palindromic_Tree a1;
int main()
{
Pow[1] = 1;
for(int i=2;i<=MAXN;i++)
{
Pow[i] = (Pow[i-1]*10)%mod;
}
a1.init();
scanf("%s",a);
int len= strlen(a);
ans = 0;
for(int i=0;i<len;i++)
{
a1.add(a[i]);
}
printf("%lld\n",ans);
return 0;
}
G 有n间房间 每间房间有a[i]个灯泡，现在每天会买k个，有v个询问，每次询问第p天已经安装好的房间数和剩余的灯泡数，只有当前留有的灯泡数大于等于某一个房间的灯泡时才会进行安装，安装是按照输入顺序依次进行的。
用线段树维护区间最小值+单点更新即可。
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson rt<<1
#define rson rt<<1|1
#define MID int m = (l+r)/2;
const int N =200000;
struct node
{
int v;
} tree[N<<2];
int a[N],op[N],ans1[N],ans2[N];
void push_up(int rt)
{
tree[rt].v = min(tree[lson].v,tree[rson].v);
}
void update(int rt,int l,int r,int p,int val)
{
if(l==r&&l==p)
{
tree[rt].v = val;
return ;
}
MID
if(p<=m)update(lson,l,m,p,val);
else update(rson,m+1,r,p,val);
push_up(rt);
}
void build(int rt,int l,int r)
{
if(l>r)return;
if(l==r)
{
tree[rt].v = a[l];
return ;
}
MID
build(lson,l,m);
build(rson,m+1,r);
push_up(rt);
}
int query(int rt,int l,int r,int val)
{
if(l==r)return l;
MID
if(tree[lson].v<=val) return query(lson,l,m,val);
if(tree[rson].v<=val)return query(rson,m+1,r,val);
return -1;
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
// update(1,1,n,i,a[i]);
}
build(1,1,n);
int v;
cin>>v;
int mx = 0;
for(int i=1; i<=v; i++)
{
scanf("%d",&op[i]);
mx = max(mx,op[i]);
}
int tt = 0;
int tmp = 0;
for(int i=1; i<=mx; i++)
{
tmp+=k;
while(1)
{
int h = query(1,1,n,tmp);
if(h==-1)
{
//tt++;
ans1[i] = tt;
ans2[i] = tmp;
break;
}
else
{
tt++;
tmp-=a[h];
ans1[i] = tt;
ans2[i] = tmp;
update(1,1,n,h,0x3f3f3f3f);
}
}
}
for(int i=1; i<=v; i++)
{
printf("%d %d\n",ans1[op[i]],ans2[op[i]]);
}
return 0;
}
J 6发罚时 题目链接 https://nanti.jisuanke.com/t/30999
学长o(n)素数筛模板 https://blog.csdn.net/a15110103117/article/details/81637569
my_code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e7+2;
bool vis[N];
long long p[N],f[N];
void init()
{
int i,i1;
memset(vis,0,sizeof(vis));
f[1] = 1;
//f[0] =1;
int top=0;
for(i=2;N>=i;i++)
{
if(vis[i]==0)
{
p[top++]=i;
f[i] = 2;
}
for(i1=0;top>i1&&N>=p[i1]*i;i1++)
{
vis[i*p[i1]]=1;
if(i%p[i1])//i里面没有一个p[i1]因子
{
f[i*p[i1]] = f[p[i1]]*f[i];
}
else
{
//if(i%(p[i1]*p[i1]))
if((i/p[i1])%p[i1]==0)//i*p[i1]里面有两个及以上的因子
{
f[i*p[i1]] = 0;
}
else //i里面仅有一个p[i1]因子
{
f[i*p[i1]] = f[i/p[i1]];
}
break;
}
}
}
// cout<<top-1<<endl;
for(int i=2;i<=N;i++)
{
f[i] = f[i-1]+f[i];
}
}
int main()
{
init();
int T;
cin>>T;
while(T--)
{
int n;cin>>n;
cout<<f[n]<<endl;
}
return 0;
}
L 赛中被pair卡常
补题链接:https://blog.csdn.net/axuhongbo/article/details/82289535
看到了别人另一种做法，也挺好
博客链接
https://blog.csdn.net/albertluf/article/details/82291234
L. Magical Girl Haze
把每个点拆成k+1个点建立分层图，对于第i个点，拆成i,i+n,i+2*n...i+k*n
若原图中i~j有一条权值为x的边，则
add_edge(i,j,x),add_edge(i+n,j+n,x).....add_edge(i+k*n,j+k*n,x) add_edge(i,j+n,0),add_edge(i+n,j+2*n,0)....add_edge(i+(k-1)*n,j+k*n,0) 每向上走一层相当于走了一条权值为0的边， 假设走了(i,j+n,0)相当于从第0层走到了第一层，而把i~j这条边的权值改为0。 最后输出1~(k+1)*n的最短路即可。my_code
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
long long dist[N][15];
const long long inf = 1e18+7;
typedef pair<int,long long >ppi;
int top,head[N*2];
int n,m,k;
struct node
{
int u,v;
long long w;
int next;
} edge[N*2];
struct pp{
int v;
long long w;
pp(int _v=0,long long _w=0):v(_v),w(_w){}
bool operator<(const pp&h)const
{
return w>h.w;
}
};
void addedge(int u,int v,long long w)
{
edge[top].v = v;
edge[top].w = w;
edge[top].next = head[u];
head[u] = top++;
}
void dijkstra()
{
priority_queue<pp>o;
for(int i=1; i<=n; i++)
{
for(int j=0; j<=12; j++)
{
dist[i][j] = inf;
}
}
for(int i=0; i<=10; i++)
{
dist[1][i] = 0;
}
o.push(pp(1,0));
while(!o.empty())
{
pp tmp =o.top();
// printf("%d%d\n",o.top().first,o.top().second);
o.pop();
int u = tmp.v;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
// printf("%d\n",i);
int v = edge[i].v;
long long w = edge[i].w;
if(dist[u][0]+w<dist[v][0])
{
dist[v][0] = dist[u][0]+w;
o.push(pp(v,dist[v][0]));
}
for(int j=1; j<=k; j++)
{
if(dist[u][j]+w<dist[v][j])
{
dist[v][j] = dist[u][j]+w;
o.push(pp(v,dist[v][j]));
}
if(dist[u][j-1]<dist[v][j])
{
dist[v][j] = dist[u][j-1];
o.push(pp(v,dist[v][j]));
}
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
memset(head,-1,sizeof(head));
top = 0;
for(int i=1; i<=m; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
}
dijkstra();
// for(int i=1;i<=n;i++)
// {
// for(int j=0;j<=k;j++)
// {
// printf("%d ",dist[i][j]);
// }
// printf("\n");
// }
long long ans = inf;
for(int i=0;i<=k;i++)
{
ans = min(dist[n][i],ans);
}
printf("%lld\n",ans);
}
return 0;
}
京公网安备 11010502036488号