2019/11/09 TZOJ

1001 Interesting Integers

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=4731

给你[a,b]区间，问有几个数是有趣的数（数字只有一个数不同的），臣妾不行；

1002 Longest Prefix

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=3559

1003 Count Color

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6036

t种颜色上到原色为颜色1的板子上面。线段树

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 ll add[maxn<<];

 ll ans[maxn<<];

 void update(int rt)

 {

     ans[rt]=ans[rt<<]|ans[rt<<|];

 }

 void Push(int rt)

 {

     if(add[rt])

     {

         add[rt<<]=add[rt];

         add[rt<<|]=add[rt];

         ans[rt<<]=add[rt];

         ans[rt<<|]=add[rt];

         add[rt]=;

     }

 }

 void buildtree(int left,int right,int rt)

 {

     add[rt]=;

     if(left==right)

     {

         ans[rt]=;

         return;

     }

     int mid=(left+right)>>;

     buildtree(left,mid,rt<<);

     buildtree(mid+,right,rt<<|);

     update(rt);

 }

 void updatetree(int a,int b,int c,int Left,int Right,int rt)

 {

     if(a<=Left&&b>=Right)

     {

         add[rt]=<<(c-);

         ans[rt]=<<(c-);

         return;

     }

     Push(rt);

     int mid=(Left+Right)>>;

     if(a<=mid) updatetree(a,b,c,Left,mid,rt<<);

     if(mid<b) updatetree(a,b,c,mid+,Right,rt<<|);

     update(rt);

 }

 ll query(int a,int b,int Left,int Right,int rt)

 {

     if(a<=Left&&b>=Right) return ans[rt];

     Push(rt);

     int mid=(Left+Right)>>;

     ll res=;

     if(a<=mid) res|=query(a,b,Left,mid,rt<<);

     if(mid<b) res|=query(a,b,mid+,Right,rt<<|);

     return res;

 }

 int main()

 {

     int L,T,O;scanf("%d%d%d",&L,&T,&O);

     buildtree(,L,);

     while(O--)

     {

         getchar();

         char ch;scanf("%c",&ch);

         if(ch=='C')

         {

             int a,b,c;scanf("%d%d%d",&a,&b,&c);

             if(a>b) swap(a,b);

             updatetree(a,b,c,,L,);

         }

         else{

             int a,b;scanf("%d%d",&a,&b);

             if(a>b) swap(a,b);

             ll res=query(a,b,,L,);

             ll num=;

             while(res)

             {

                 if(res&) num++;

                 res>>=;

             }

             printf("%lld\n",num);

         }

     }

 }

1004 Get Many Persimmon Trees

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6045

二维树状数组，以(s,t)的矩形暴力找过去，得到最大的ans。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define N 105

 int ma[N][N];

 int n,m;

 inline int lowbit(int x){return x&-x;}

 void updata(int x,int y)

 {

     for(int i=x;i<=n;i+=lowbit(i))

         for(int j=y;j<=m;j+=lowbit(j)) ma[i][j]++;

 }

 int query(int x,int y)

 {

     int res=;

     for(int i=x;i>;i-=lowbit(i))

         for(int j=y;j>;j-=lowbit(j)) res+=ma[i][j];

     return res;

 }

 int main()

 {

     int T;

     while(~scanf("%d",&T),T)

     {

         scanf("%d%d",&n,&m);

         memset(ma,,sizeof(ma));

         while(T--)

         {

             int a,b;scanf("%d%d",&a,&b);

             updata(a,b);

         }

         int s,t;scanf("%d%d",&s,&t);

         int ans=;

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

             for(int j=;j<=m;j++)

             {

                 int upi=i,upj=j,downi=i+s-,downj=j+t-;

                 if(downi>n||downj>m) continue;

                 int sum=query(upi-,upj-)+query(downi,downj)-query(downi,upj-)-query(upi-,downj);

                 ans=ans>sum?ans:sum;

             }

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

     }

 }

1005 Travelling

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6062

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define N 60005

 int mp[][],n,m,ans,dp[][N];

 int in[],three[];

 void init(int n)

 {

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

     {

         for(int j=;j<in[n];j++)

             dp[i][j]=-;

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

             mp[i][j]=-;

     }

 }

 int arr(int three[],int sum)

 {

     int res=;

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

     {

         three[i]=sum%;

         sum/=;

         if(three[i]) res++;

     }

     return res;

 }

 void bfs()

 {

     for(int kk=;kk<in[n];kk++)

     {

         int k=arr(three,kk);

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

         {

             if(three[i])

             {

                 if(k==) dp[i][kk]=;

                 if(dp[i][kk]==-) continue;

                 if(k==n)

                 {

                     if(ans==-) ans=dp[i][kk];

                     else ans=min(ans,dp[i][kk]);

                 }

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

                 {

                     if(i!=j&&three[j]<&&mp[i][j]!=-)

                     {

                         int mark=kk+in[j];

                         if(dp[j][mark]==-) dp[j][mark]=dp[i][kk]+mp[i][j];

                         else dp[j][mark]=min(dp[i][kk]+mp[i][j],dp[j][mark]);

                     }

                 }

             }

         }

     }

 }

 int main()

 {

     in[]=;

     for(int i=;i<=;i++) in[i]=in[i-]*;

     while(~scanf("%d%d",&n,&m))

     {

         init(n);

         while(m--)

         {

             int a,b,c;scanf("%d%d%d",&a,&b,&c);

             a--,b--;

             if(mp[a][b]!=-) mp[a][b]=mp[b][a]=min(mp[a][b],c);

             else mp[a][b]=mp[b][a]=c;

         }

         ans=-;

         bfs();

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

     }

 }

1006 A/B

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6065

(A/B)%MOD->(A%MOD)*(B-1%MOD)

这里用了求出m的欧拉函数值再进行一次快速幂f(b,phi[M]-1)求逆元

 #include<bits/stdc++.h>

 using namespace std;

 const int M=;

 typedef long long ll;

 ll phi[];

 void euler()

 {

     for(int i=;i<=M;++i)

         phi[i]=i;

     for (int i=;i<=M;i++)

         if (phi[i]==i)

             for (int j=i;j<=M;j+=i)

                 phi[j]=phi[j]/i*(i-);

 }

 ll f(ll a,ll b)

 {

     ll res=,x=a%M;

     while(b)

     {

         if(b&) res=(res*x)%M;

         b>>=;

         x=x*x%M;

     }

     return res;

 }

 int main()

 {

     euler();

     int t;scanf("%d",&t);

     while(t--)

     {

         ll n,b;scanf("%lld%lld",&n,&b);

         printf("%lld\n",n*f(b,phi[M]-)%M);

     }

 }

拓展欧几里得算法，a*x+b*y=GCD，当a==GCD,b==0时停止查找，可推出最后状态a*1+b*0==GCD。前后等式分别为a*x+b*y=gcd、b*x1+(a%b)*y1=gcd，补上条件递归。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int M=;

 ll ans,re;

 void e_gcd(ll a,ll b)

 {

     if(b==)

     {

         ans=,re=;

         return;

     }

     e_gcd(b,a%b);

     ll temp=ans;

     ans=re;

     re=temp-a/b*re;

 }

 int main()

 {

     int t;scanf("%d",&t);

     while(t--)

     {

         ll n,b;scanf("%lld%lld",&n,&b);

         e_gcd(b,M);

         ans<?ans+=M:ans+=;

         printf("%lld\n",n*ans%M);

     }

 }

1007 Road Construction

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6085

缩点，(叶子节点+1)/2

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define N 1005

 vector<int> G[N];

 int n,r,low[N],degree[N],mp[N][N],cnt;

 void init()

 {

     for(int i=;i<=n;i++) G[i].clear();

     memset(low,,sizeof(low));

     memset(degree,,sizeof(degree));

     memset(mp,,sizeof(mp));

 }

 void dfs(int u,int x)

 {

     int l=G[u].size();

     low[u]=cnt++;

     for(int i=;i<l;i++)

     {

         int v=G[u][i];

         if(v==x) continue;

         if(!low[v]) dfs(v,u);

         low[u]=min(low[u],low[v]);

     }

 }

 int tarjan()

 {

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

     {

         int l=G[i].size();

         for(int j=;j<l;j++)

             if(low[i]!=low[G[i][j]]) degree[low[i]]++;

     }

     int res=;

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

         if(degree[i]==) res++;

     return res;

 }

 int main()

 {

     scanf("%d%d",&n,&r);

     init();

     while(r--)

     {

         int a,b;scanf("%d%d",&a,&b);

         if(mp[a][b]) continue;

         mp[a][b]=mp[b][a]=;

         G[a].push_back(b),G[b].push_back(a);

     }

     cnt=;

     dfs(,);

     int res=tarjan();

     printf("%d\n",(res+)/);

 }

1008 Currency Exchange

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6097

spfa算法，判断是否存在环路。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define N 105

 double ma1[N][N],ma2[N][N],ans[N];

 int n,m,s,a,b;

 int vis[N];

 double v,x_ab,x_ba,y_ab,y_ba;

 bool spfa()

 {

     ans[s]=v;

     vis[s]=;

     queue<int> qu;

     qu.push(s);

     while(!qu.empty())

     {

         int node=qu.front();

         qu.pop();

         vis[node]=;

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

         {

             if(ans[i]<(ans[node]-ma2[node][i])*ma1[node][i])

             {

                 ans[i]=(ans[node]-ma2[node][i])*ma1[node][i];

                 if(ans[s]>v) return true;

                 if(!vis[i]) qu.push(i),vis[i]=;

             }

         }

     }

     return false;

 }

 void init()

 {

     memset(vis,,sizeof(vis));

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

     {

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

         {

             ma1[i][j]=;

             ma2[i][j]=ma1[i][j]=;

         }

     }

 }

 int main()

 {

     scanf("%d%d%d%lf",&n,&m,&s,&v);

     init();

     for(int kk=;kk<m;kk++)

     {

         scanf("%d%d%lf%lf%lf%lf",&a,&b,&x_ab,&y_ab,&x_ba,&y_ba);

         ma1[a][b]=x_ab,ma2[a][b]=y_ab;

         ma1[b][a]=x_ba,ma2[b][a]=y_ba;

     }

     if(spfa()) printf("YES\n");

     else printf("NO\n");

 }

巴特西

2019/11/09 TZOJ

最新文章

热门文章