解题报告：

　　傻逼错误天天犯QAQ

　　第一题：简单DP，f[i][j]表示第 i 道题选 j 的最大得分，可以从f[i-1][j-1],f[i-1][j],f[i-1][j+1]转移过来，其实是可以滚动数组优化空间的，不过懒得弄了=。=反正能过

 //TYVJ A

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 typedef long long LL;

 const int N=,INF=~0u>>;

 /*******************template********************/

 int n,a[N],c[N],f[N][];

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("input.txt","r",stdin);

 //    freopen("output.txt","w",stdout);

 #endif

     n=getint();

     char s[];

     F(i,,n){

         scanf("%s",s);

         a[i]=s[]-'A'+;

         c[i]=getint();

     }

     F(i,,n) F(j,,){

         f[i][j]=max(f[i-][j-],max(f[i-][j],f[i-][j+]))+

             (j==a[i]?c[i]:);

     }

     int ans=;

     F(j,,) ans=max(f[n][j],ans);

     printf("%d\n",ans);

     return ;

 }

　　第二题：数论题：求$$\sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)是无平方因子的数]*gcd(i,j)$$

　　昂……蒟蒻实在太弱了就爆零了= =

UPD：2015年5月1日 22:18:17

　　题解：http://pan.baidu.com/s/1eQvTApW

　　写法是学习的hzwer的……因为$n\leq 150W$所以其实筛出μ以后直接暴算g即可……反正O(nlogn)是不会爆的0.0

 //TYVJ B

 #include<cmath>

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 typedef long long LL;

 const int N=,INF=~0u>>;

 /*******************template********************/

 int prime[N],tot,n,m,f[N],mu[N];

 LL g[N];

 bool check[N];

 void getmu(int n){

     mu[]=;

     F(i,,n){

         if (!check[i]){

             prime[++tot]=i;

             mu[i]=-;

         }

         F(j,,tot){

             if (i*prime[j]>n) break;

             check[i*prime[j]]=;

             if (i%prime[j]==){

                 mu[i*prime[j]]=;

                 break;

             }else mu[i*prime[j]]=-mu[i];

         }

     }

     F(i,,n) if (mu[i]) f[i]=i;

     F(i,,n) if (f[i])

         for(int j=;j*i<=n;j++)

             g[j*i]+=f[i]*mu[j];

     F(i,,n) g[i]+=g[i-];

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("B.in","r",stdin);

 //    freopen("output.txt","w",stdout);

 #endif

     int T=getint();

     getmu();

     while(T--){

         n=getint(); m=getint();

         LL ans=;

         if (n>m) swap(n,m);

         for(int i=,last;i<=n;i=last+){

             last=min(n/(n/i),m/(m/i));

             ans+=(g[last]-g[i-])*(n/i)*(m/i);

         }

         printf("%I64d\n",ans);

     }

     return ;

 }

 //必须保证单次询问O(sqrt(N))的时间内搞定

　　第三题：询问到树上两点距离$\leq K$的点的个数，强制在线。

　　= =蒟蒻实在太弱，只能捡上白送的60分跑。

　　60分做法：$n\leq 1000$，所以$n^2$的做法即可，那么处理出来dist[i][j]即任意两点间的距离，每次查询O(n)枚举即可，因为是树上距离，所以以每个点为根dfs一次即可求出dist[i][j]。

　　第四题：太神了不会做，听说要用FWT？

　　第五题：经典毒瘤题= =（神犇们都说是大水题Orz）因为取模每次必然使数折半，所以每个数最多取模log(a[i])次，那么每个数可以视为一开始有log(a[i])的能量，每次取模能量-1，单点修改可以视为给这个数重新充能。

　　所以只要用线段树维护区间最大值（便于确定哪些数不用取模）和区间和，每次取模时在线段树上一路走到叶子进行修改，就可以AC啦~

　　我是SB：每次query之前忘记把ans清零了！！！！f**k，一句话爆零系列。

 //TYVJ E

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 typedef long long LL;

 LL getLL(){

     LL v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,INF=~0u>>;

 /*******************template********************/

 LL mx[N<<],sum[N<<],a[N],n,m;

 #define L (o<<1)

 #define R (o<<1|1)

 #define mid (l+r>>1)

 void maintain(int o,int l,int r){

     if (l==r) return;

     mx[o]=max(mx[L],mx[R]);

     sum[o]=sum[L]+sum[R];

 }

 void build(int o,int l,int r){

     if (l==r) {

         sum[o]=mx[o]=a[l];

     }else{

         build(L,l,mid);

         build(R,mid+,r);

         maintain(o,l,r);

     }

 }

 void update(int o,int l,int r,int pos,LL v){

     if (l==r) a[l]=mx[o]=sum[o]=v;

     else{

         if (pos<=mid) update(L,l,mid,pos,v);

         else update(R,mid+,r,pos,v);

         maintain(o,l,r);

     }

 }

 int ql,qr;

 void modify(int o,int l,int r,LL x){

     if (ql>r || qr<l) return;

     if (mx[o]<x) return;

     if (l==r) a[l]=mx[o]=sum[o]=a[l]%x;

     else{

         modify(L,l,mid,x);

         modify(R,mid+,r,x);

         maintain(o,l,r);

     }

 }

 LL ans;

 void query(int o,int l,int r){

     if (ql<=l && qr>=r) ans+=sum[o];

     else{

         if (ql<=mid) query(L,l,mid);

         if (qr>mid) query(R,mid+,r);

     }

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("E.in","r",stdin);

 //    freopen("output.txt","w",stdout);

 #endif

     n=getLL(); m=getLL();

     F(i,,n) a[i]=getLL();

     build(,,n);

     LL cmd,l,k,x;

     F(i,,m){

         cmd=getLL(); l=getLL(); k=getLL();

         if (cmd==){

             ql=l; qr=k; ans=;

             query(,,n);

             printf("%I64d\n",ans);

         }else if (cmd==){

             x=getLL();

             ql=l; qr=k;

             modify(,,n,x);

         }else{

             update(,,n,l,k);

         }

     }

     return ;

 }

巴特西

【tyvj五月有奖赛暨Loi 55 Round #1】

解题报告：

最新文章

热门文章

巴特西

【tyvj五月有奖赛 暨Loi 55 Round #1】

解题报告：

最新文章

热门文章

【tyvj五月有奖赛暨Loi 55 Round #1】