博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
2011 Multi-University Training Contest 4 - Host by SDU
阅读量：4982 次
发布时间：2019-06-12

本文共 12231 字，大约阅读时间需要 40 分钟。

A.(polya计数+字符串匹配)

此题的难点在于确定置换的个数，由a[i+k]=a[i], e[i+k]=e[i]联想到KMP。

于是把原串和原串扩大两倍的目标串进行字符串匹配就能求出具体的置换。

这里的算法可以使用hash或者kmp。

然后套polya公式就行了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for((i) = 0; (i) < (n); ++(i))#define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i))#define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i))#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%lld\n", x)#define Read() freopen("data.in", "r", stdin)#define Write() freopen("data.out", "w", stdout);typedef long long LL;const double eps = 1e-6;const double PI = acos(-1.0);const int inf = 0x1F1F1F1F;using namespace std;const int N = 100010;const int MOD = 1000000007;int n;int pre[N];bool vis[2][N];int v[N], e[N];int vv[N<<1], ee[N<<1];void get_next(int P[]) { int i, j = -1; pre[0] = -1; for(i = 1; i < n; ++i) { while(j > -1 && P[j+1] != P[i]) j = pre[j]; if(P[j + 1] == P[i]) ++j; pre[i] = j; }}void kmp(int T[], int P[], int f) { get_next(P); int i, k; for(k = -1, i = 0; i < (n<<1); ++i) { while(k > -1 && P[k+1] != T[i]) k = pre[k]; if(P[k+1] == T[i]) ++k; if(k == n - 1) { vis[f][i - n + 1] = true; k = pre[k]; } }}LL Pow(LL a, int b) { LL res = 1; while(b) { if(b&1) res = (res*a)%MOD; a = (a*a)%MOD; b >>= 1; } return res;}int exp_gcd(int a, int b, int& x, int& y) { if(b == 0) { x = 1; y = 0; return a; } int d = exp_gcd(b, a%b, y, x); // x1 = y2, y1 = x2; y -= a/b*x; //y1 = x2 - (a/b)*y2 return d;}int Inv(int c) { int x, y; exp_gcd(c, MOD, x, y); return x < 0 ? x + MOD : x;}int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b);}int main() { //Read(); int T, c, cnt, i; LL ans; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &c); for(i = 0; i < n; ++i) {scanf("%d", &v[i]); vv[i] = vv[i+n] = v[i];} for(i = 0; i < n; ++i) {scanf("%d", &e[i]); ee[i] = ee[i+n] = e[i];} CL(vis, false); kmp(vv, v, 0); kmp(ee, e, 1); ans = cnt = 0; for(i = 1; i <= n; ++i) { if(vis[0][i] && vis[1][i]) { ans += Pow(c, gcd(i, n)); ans %= MOD; cnt++; //cout << pow(c, gcd(i, n)) << " " << gcd(i, n) << endl; } } ans = ans*Inv(cnt)%MOD; cout << ans << endl; } return 0;}
View Code

 

B.(平面图最小割转对偶图最短路)

BZOJ 狼抓兔子的简化版。

 

C.(待填坑)

 

D.(线段树和单调栈优化DP)

容易得到DP方程 dp[i]=dp[j]+max(val[j+1,i]) (pre[i]<=j<i).

复杂度为O(n^2logn) 需要优化。

方程右边的max()可以通过单调栈O(n)求出。复杂度O(n^2).

我们可以发现，假设此时扫到了k 对于单调栈里维护的两个连续的数 a[i]和a[j] (i>j) 那么max[[j+1,i], k]=a[i].

此时这些转移点的右边最大值部分都是一样的，那么我们只要求出这些转移点的dp部分最小值就行了。用一个线段树维护dp值，可以在logn的时间求出。

但是这样还是行不通，一个单调递减序列足以达到最坏复杂度。

 可以再用一个线段树来维护min(dp[j]+max(...))。

复杂度O(nlogn).

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                using namespace std;#define inf 0x3f3f3f3f#define Max 100100int max(int a,int b){ return a>b?a:b;}int min(int a,int b){ return a
                 
                  >1; }}T[4*Max];void build(int l,int r,int rt){ T[rt].l=l;T[rt].r=r; T[rt].minx=0; if(l==r) { // T[rt].max=val[l]; return ; } int mid=T[rt].mid(); build(l,mid,rt<<1); build(mid+1,r,rt<<1|1);}void modify(int l,int rt,int data){ if(T[rt].l==T[rt].r) { T[rt].minx=data; return; } int mid=T[rt].mid(); if(l<=mid) modify(l,rt<<1,data); else modify(l,rt<<1|1,data); T[rt].minx=min(T[rt<<1].minx,T[rt<<1|1].minx);}void query(int l,int r,int rt){ if(T[rt].l==l&&T[rt].r==r) { rec=min(rec,T[rt].minx); return; } int mid=T[rt].mid(); if(l>=mid+1) query(l,r,rt<<1|1); else if(r<=mid) query(l,r,rt<<1); else { query(l,mid,rt<<1); query(mid+1,r,rt<<1|1); }}int main(){ int i,j; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&typ[i]); } for(i=1;i<=n;i++) { scanf("%d",&val[i]); } dp[0]=0; int top=0;int tail=1; build(0,n,1); q[0]=0; memset(lef,0,sizeof(lef)); for(i=1;i<=n;i++) { // int maxn=val[i]; while(tail>top+1&&val[i]>val[q[tail-1]]) tail--; q[tail]=i; tail++; dp[i]=inf; for(j=tail-1;j>top&&q[j]>lef[typ[i]];j--) { rec=inf; query(max(q[j-1],lef[typ[i]]),q[j]-1,1); // printf("a"); dp[i]=min(rec+val[q[j]],dp[i]); } modify(i,1,dp[i]); lef[typ[i]]=i; // printf("i %d dp %d\n",i,dp[i]); } printf("%d\n",dp[n]); }}
View Code

 

E.(最短路变形)

这是个具有保护节点的最短路。 每个节点必须在到达他的所有前置节点之后才能访问它。

考虑在 堆优化dijkstra 判断入堆条件时 多加几个判断就ok了

# include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             # include 
              
               # include 
               
                # include 
                
                 using namespace std;# define lowbit(x) ((x)&(-x))# define pi acos(-1.0)# define eps 1e-3# define MOD 100000007# define INF ((LL)1<<60)# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i
                 
                   PII;typedef vector
                  
                    VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=3005;//Code begin...struct Edge{ int p, next, w;}edge[140005];int head[N], cnt, num[N];VI node[N];bool vis[N];LL dis[N], mark[N];struct qnode{ int v; LL c; qnode(int _v=0,LL _c=0):v(_v),c(_c){} bool operator <(const qnode &r)const{ return c>r.c;}};void init(){ mem(head,0); cnt=1; mem(num,0); FO(i,0,N) node[i].clear();}void add_edge(int u, int v, int w){ edge[cnt].p=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;}void dij(int n, int start){ mem(vis,0); mem(mark,0); FOR(i,1,n) dis[i]=INF; priority_queue
                   
                    que; while (!que.empty()) que.pop(); dis[start]=0; que.push(qnode(start,0)); qnode tmp; while (!que.empty()) { tmp=que.top(); que.pop(); int u=tmp.v; if (vis[u]) continue; FO(i,0,node[u].size()) { int v=node[u][i]; --num[v]; if (num[v]==0&&mark[v]) dis[v]=max(mark[v],dis[u]), que.push(qnode(v,dis[v])); } vis[u]=1; for (int i=head[u]; i; i=edge[i].next) { int v=edge[i].p; if (num[v]) { if (!mark[v]) mark[v]=dis[u]+edge[i].w; else mark[v]=min(mark[v],dis[u]+edge[i].w); } if (!num[v]&&!vis[v]&&dis[v]>dis[u]+edge[i].w) { dis[v]=dis[u]+edge[i].w; que.push(qnode(v,dis[v])); } } }}int main (){ int T, n, m, u, v, w; scanf("%d",&T); while (T--) { init(); scanf("%d%d",&n,&m); while (m--) scanf("%d%d%d",&u,&v,&w), add_edge(u,v,w); FOR(i,1,n) { scanf("%d",num+i); FOR(j,1,num[i]) scanf("%d",&u), node[u].pb(i); } dij(n,1); printf("%lld\n",dis[n]); } return 0;}
View Code

 

F.(离线+树状数组)

BZOJ HH的项链的变形。

 

G.(数论综合)

题目需要求sigma(lcm(i,n))-sigma(gcd(i,n))是否能被c整除。

结合欧拉函数和积性函数可以推出这两个式子，最后用大整数质因子分解算法可以算出答案。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           const int TIME = 12;long long factor[100],fac_num[100];int count;int cmp(const void *a,const void *b){    long long temp;    temp = *(long long*)a-*(long long *)b;    if(temp==0)     return 0;    else if(temp<0)     return -1;    else return 1;}long long gcd(long long a,long long b){    if(b==0) return a;    return gcd(b,a%b);}long long multi_mod(long long a,long long b,long long n){    long long res = 0;    a%=n;    for(;b;b>>=1)    {      if(b&1)        res = (res+a)%n;      a<<=1;      a%=n;    }    return res;}long long multi_exp(long long a,long long b,long long n){    long long res = 1;    for(;b;b>>=1)    {       if(b&1)         res = multi_mod(res,a,n);       a = multi_mod(a,a,n);    }    return res;}bool witness(long long a,long long n){   long long  m,x,y;   int i,j = 0;   m = n-1;   while(m%2==0)   {       j++;       m>>=1;   }   x = multi_exp(a,m,n);   for(i = 1;i<=j;i++)   {       y = multi_exp(x,2,n);       if(y==1&&x!=1&&x!=n-1)         return false;       x = y;   }   if(y!=1)     return false;   return true;}bool Miller_Rabin(long long n,int times){    int i;    long long a;    if(n==1)      return false;    if(n==2)      return true;    if(n%2==0)      return false;    for(i = 1;i<=times;i++)    {        a = rand()%(n-2)+2;        if(!witness(a,n))          return false;    }    return true;}long long pollard_rho(long long n){    long long i = 1, x = (long long)fabs(1.0*(rand() % (n - 1))) + 1, y, k, d, c;    y = x, k = 2;    do { c = (long long)fabs(1.0*(rand() % (n - 1))) + 1; } while (c == 0 || c == 2);    do    {        i++;        d = gcd(n + y - x, n);        if (d != 1 && d != n) return d;        if (i == k) y = x, k <<= 1;        x = (multi_mod(x, x, n) + n - c) % n;    } while (y != x);    return n;}void get_factor(long long n){    long long temp;    if(n==1)     return ;    if(Miller_Rabin(n,TIME)==true)    {     factor[count++] = n;     return ;    }    temp = n;    while(temp>=n)    temp = pollard_rho(temp);    get_factor(temp);    get_factor(n/temp);}int main(){    long long n,c,temp1,temp2,temp3,keep;    int count1,i,count2,T;    srand(time(NULL));    scanf("%d",&T);    while(T--)    {        scanf("%I64d%I64d",&n,&c);        count = 0;        get_factor(n);        qsort(factor,count,sizeof(factor[0]),cmp);        count1 = 0;        count2 = 1;        for(i = 1;i
View Code

 

H.(水题)

韦达定理。

# include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             # include 
              
               # include 
               
                # include 
                
                 using namespace std;# define lowbit(x) ((x)&(-x))# define pi acos(-1.0)# define eps 1e-3# define MOD 100000007# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i
                 
                   PII;typedef vector
                  
                    VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=10005;//Code begin...int main (){ int T; LL a, b, c; scanf("%d",&T); while (T--) { scanf("%lld%lld%lld",&a,&b,&c); LL delta=b*b-4*a*c; if (delta<0) puts("NO"); else if (delta==0) printf("%.2f\n",-(double)b/2/a); else { double m=sqrt(delta), x1=(-b-m)/2/a, x2=(-b+m)/2/a; if (x1>x2) swap(x1,x2); printf("%.2f %.2f\n",x1,x2); } } return 0;}
View Code

 

I.(水题)

结构体排序。

# include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             # include 
              
               # include 
               
                # include 
                
                 using namespace std;# define lowbit(x) ((x)&(-x))# define pi acos(-1.0)# define eps 1e-3# define MOD 100000007# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i
                 
                   PII;typedef vector
                  
                    VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=10005;//Code begin...typedef struct{LL a, b, id, sum, eq;}Node;Node node[N];bool comp(Node a, Node b){ if (a.sum!=b.sum) return a.sum>b.sum; if (a.eq!=b.eq) return a.eq>b.eq; return a.id
                   
                    node[i].b) node[i].eq=2; else if (node[i].a==node[i].b) node[i].eq=1; else node[i].eq=0; } sort(node+1,node+n+1,comp); FOR(i,1,n) { printf("%lld+%lld=[",node[i].a,node[i].b); if (node[i].eq==0) putchar('<'); else if (node[i].eq==1) putchar('='); else putchar('>'); printf("%lld]\n",node[i].sum); } puts(""); } return 0;}
View Code

 

J.(待填坑)

 

转载于:https://www.cnblogs.com/lishiyao/p/6476438.html

你可能感兴趣的文章
python--redis
查看>>
禁用input帐号密码的自动填充
查看>>
python的小技巧
查看>>
json数组转数组对象
查看>>
KMP算法详解 转帖
查看>>
Struts2+Hibernate+Spring+Webservice 项目从Tomcat到WebLogic遇到问题的解决方法
查看>>
C# 代理/委托 Delegate
查看>>
笨方法学python--参数，解包，变量
查看>>
android 加载本地图片与网络图片
查看>>
易经读书笔记17 泽雷随
查看>>
oracle正则表达式函数 匹配
查看>>
jmeter --自动化badboy脚本开发技术
查看>>
Linux驱动：LCD驱动测试
查看>>
Mark Down 尝试
查看>>
第三节：使用Log4net和过滤器记录异常信息，返回异常给前端
查看>>
fedora的选择
查看>>
AlphaPose论文笔记《RMPE: Regional Multi-person Pose Estimation》
查看>>
模糊查询和聚合函数
查看>>
[批处理]批量将文件名更名为其上级目录名
查看>>
如何查找ORACLE中的跟踪文件
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-09 00:12:20   当前IP: 18.117.76.255   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我