1001
思路：首先把m个x分解成x*（m个1）
显然这样直接mod不行
又=(（10^m-1)mod(k*9))/9
然后快速幂，同余运算
1 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <cmath> 9 #include <set> 10 #include <algorithm> 11 #include <vector> 12 #include <map> 13 // #include<malloc.h> 14 using namespace std; 15 #define clc(a,b) memset(a,b,sizeof(a)) 16 #define LL long long 17 const int inf = 0x3f3f3f3f; 18 const double eps = 1e-5; 19 // const double pi = acos(-1); 20 const LL MOD = 9901; 21 const int N = 110; 22 23 // inline int r(){ 24 // int x=0,f=1;char ch=getchar(); 25 // while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();} 26 // while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 27 // return x*f; 28 // } 29 30 LL pow_m(LL a,LL b,LL MOD){ 31 LL ans = 1; 32 a %= MOD; 33 while(b) 34 { 35 if(b & 1) 36 { 37 ans = ans * a % MOD; 38 b--; 39 } 40 b >>= 1; 41 a = a * a % MOD; 42 } 43 return ans; 44 } 45 46 47 int main(){ 48 int T; 49 LL x,m,k,c; 50 LL ans; 51 int cas; 52 cas=1; 53 scanf("%d",&T); 54 while(T--){ 55 scanf("%I64d%I64d%I64d%I64d",&x,&m,&k,&c); 56 k*=9; 57 ans=(pow_m(10,m,k)+k-1)%k; 58 ans/=9; 59 k/=9; 60 ans=(ans*x)%k; 61 printf("Case #%d:\n",cas++); 62 if(ans==c) 63 printf("Yes\n"); 64 else 65 printf("No\n"); 66 } 67 return 0; 68 }
另一种做法是找循环节
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 typedef long long ll; 7 ll vis[20000]; 8 ll ans[20000]; 9 int main(){ 10 int t; 11 scanf("%d",&t); 12 int kase=0; 13 while(t--){ 14 ll x,m,k,c; 15 scanf("%I64d%I64d%I64d%I64d",&x,&m,&k,&c); 16 printf("Case #%d:\n",++kase); 17 memset(vis,0,sizeof(vis)); 18 memset(ans,0,sizeof(ans)); 19 ll tmp=0; 20 ll len=0; 21 for(ll i=1;i<=m;i++){ 22 tmp=tmp*10+x; 23 if(!vis[tmp%k]){ 24 vis[tmp%k]=1; 25 ans[i]=tmp%k; 26 } 27 else{ 28 len=i; 29 break; 30 } 31 tmp=tmp%k; 32 } 33 if(!len){ 34 len=m; 35 } 36 ll kk=m%len; 37 if(kk==0)kk=len; 38 if(ans[kk]==c){ 39 cout<<"Yes"<<endl; 40 }else{ 41 cout<<"No"<<endl; 42 } 43 } 44 return 0; 45 }
1006
Gym Class
思路：先想一下，肯定是分数高的同学在前面先出来，怎样选择分数高的呢？
如果b不能出现先a的前面，我们可以建一条边，由a指向b，那么最后入度为0的点肯定是先出队，并且ID最高，这里用优先队列维护。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <sstream> 5 #include <string> 6 #include <algorithm> 7 #include <list> 8 #include <map> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <cstdlib> 14 #include <conio.h> 15 using namespace std; 16 #define clc(a,b) memset(a,b,sizeof(a)) 17 #define inf 0x3f3f3f3f 18 const int N=100010; 19 const int MOD = 1e9+7; 20 #define LL long long 21 double const pi = acos(-1); 22 void fre() { 23 freopen("in.txt","r",stdin); 24 } 25 26 // inline int r() { 27 // int x=0,f=1;char ch=getchar(); 28 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 29 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 30 // } 31 vector<int>g[N]; 32 int d[N]; 33 bool vis[N]; 34 int ans[N]; 35 int main(){ 36 // fre(); 37 int T; 38 scanf("%d",&T); 39 while(T--){ 40 priority_queue<int>q; 41 int n,m; 42 scanf("%d%d",&n,&m); 43 for(int i=0;i<=n;i++) g[i].clear(); 44 for(int i=0;i<=n;i++){ 45 vis[i]=false; 46 d[i]=0; 47 ans[i]=0; 48 } 49 for(int i=0;i<m;i++){ 50 int u,v; 51 scanf("%d%d",&u,&v); 52 g[u].push_back(v); 53 d[v]++; 54 } 55 for(int i=0;i<=n;i++){ 56 if(d[i]==0) 57 q.push(i); 58 } 59 int k=0; 60 while(!q.empty()){ 61 int f=q.top(); 62 q.pop(); 63 ans[k++]=f; 64 for(int i=0;i<(int)g[f].size();i++){ 65 int v=g[f][i]; 66 if(vis[v]==false&&d[v]>0){ 67 d[v]--; 68 // vis[v]=t; 69 // q.push(v); 70 } 71 if(d[v]==0){ 72 q.push(v); 73 vis[v]=true; 74 } 75 } 76 } 77 int minn=inf; 78 LL sum=0; 79 for(int i=0;i<k;i++){ 80 minn=min(minn,ans[i]); 81 sum+=minn; 82 } 83 printf("%lld\n",sum); 84 } 85 return 0; 86 }
1002
Sitting in Line
思路:dp[i][j]表示，i的二进制条件下，每位为1则表示a[i]已经确定，0则反之，最后一个为a[j]的最大分数。
dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+w[j]*w[k]);
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <sstream> 5 #include <string> 6 #include <algorithm> 7 #include <list> 8 #include <map> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <cstdlib> 14 #include <conio.h> 15 using namespace std; 16 #define clc(a,b) memset(a,b,sizeof(a)) 17 #define inf 0x3f3f3f3f 18 const int N=100010; 19 const int MOD = 1e9+7; 20 #define LL long long 21 double const pi = acos(-1); 22 #define bitnum(a) __builtin_popcount(a) 23 void fre() { 24 freopen("in.txt","r",stdin); 25 } 26 27 // inline int r() { 28 // int x=0,f=1;char ch=getchar(); 29 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 30 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 31 // } 32 int w[20],p[20],mapp[20]; 33 LL dp[1<<17][20]; 34 int main(){ 35 // fre(); 36 int T; 37 int cas=1; 38 int n; 39 scanf("%d",&T); 40 while(T--){ 41 42 scanf("%d",&n); 43 clc(mapp,-1); 44 for(int i=0;i<n;i++){ 45 scanf("%d%d",&w[i],&p[i]); 46 if(p[i]!=-1){ 47 mapp[p[i]]=i; 48 } 49 } 50 51 for(int i=0;i<(1<<n);i++) { 52 for(int j=0;j<n;j++) 53 dp[i][j]=-inf; 54 } 55 56 if(mapp[0]!=-1) dp[(1<<mapp[0])][mapp[0]]=0; 57 else 58 for(int i=0;i<n;i++) dp[(1<<i)][i]=0; 59 60 for(int i=1;i<(1<<n);i++){ 61 for(int j=0;j<n;j++){//a[j]最后一个数 62 if(i&(1<<j)){ 63 for(int k=0;k<n;k++){//a[k]填入 64 if((i&(1<<k))==0){ 65 int cnt=bitnum(i);//从0到cnt-1已经确定，则a[k]可以填在cnt位上或任意填 66 if(mapp[cnt]==k||mapp[cnt]==-1){ 67 dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+w[j]*w[k]); 68 } 69 } 70 } 71 } 72 } 73 } 74 75 LL ans=-inf; 76 for(int i=0;i<n;i++){ 77 // cout<<dp[(1<<n)-1][i]<<endl; 78 ans=max(ans,dp[(1<<n)-1][i]); 79 } 80 printf("Case #%d:\n%lld\n",cas++,ans); 81 } 82 return 0; 83 }
1003
BD String
dfs对称处理
[l,r]分为[1,r]-[1,l-1];
[1,x]分成三部分
比x小但最大的2^n-1的区间里B的数量+1+剩余区间里B的数量
剩余区间里B的数量=res-(ans-dfs(m-res))
res：剩余区间的长度
ans：比x小但最大的2^n-1的区间里B的数量
m=2^n-1
s=2^n-1;
s中B的数量为2^(n-1)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <sstream> 5 #include <string> 6 #include <algorithm> 7 #include <list> 8 #include <map> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <cstdlib> 14 #include <conio.h> 15 using namespace std; 16 #define clc(a,b) memset(a,b,sizeof(a)) 17 #define inf 0x3f3f3f3f 18 const int N=100010; 19 const int MOD = 1e9+7; 20 #define LL long long 21 double const pi = acos(-1); 22 #define bitnum(a) __builtin_popcount(a) 23 void fre() { 24 freopen("in.txt","r",stdin); 25 } 26 27 // inline int r() { 28 // int x=0,f=1;char ch=getchar(); 29 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 30 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 31 // } 32 33 LL dfs(LL x){ 34 if(x==0){ 35 return 0; 36 } 37 LL m=0; 38 while(m<x){ 39 m=m*2+1; 40 } 41 m=(m-1)/2; 42 LL ans=(m+1)/2; 43 LL res=x-m-1; 44 return ans+1+res-(ans-dfs(m-res)); 45 } 46 47 int main(){ 48 // fre(); 49 int T; 50 LL l,r; 51 scanf("%d",&T); 52 while(T--){ 53 scanf("%lld%lld",&l,&r); 54 LL ans=dfs(r)-dfs(l-1); 55 printf("%lld\n",ans); 56 } 57 return 0; 58 }
1004 D Game
http://blog.csdn.net/ok_again/article/details/51472659
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <sstream> 6 #include <string> 7 #include <algorithm> 8 #include <list> 9 #include <map> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <cstdlib> 15 // #include <conio.h> 16 using namespace std; 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 #define inf 0x3f3f3f3f 19 #define lson l,mid,rt<<1 20 #define rson mid+1,r,rt<<1|1 21 const int N=100010; 22 const int MOD = 1e9+7; 23 #define LL long long 24 double const pi = acos(-1); 25 void fre() { 26 freopen("in.txt","r",stdin); 27 } 28 // inline int r() { 29 // int x=0,f=1;char ch=getchar(); 30 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 31 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 32 // } 33 bool dp[301][301]; 34 int d[301]; 35 int a[301]; 36 map<int,bool> mp; 37 int main(){ 38 // fre(); 39 int T; 40 scanf("%d",&T); 41 while(T--){ 42 int n,m; 43 scanf("%d%d",&n,&m); 44 mp.clear(); 45 clc(dp,false); 46 clc(d,0); 47 for(int i=1;i<=n;i++){ 48 dp[i][i+1]=true; 49 scanf("%d",&a[i]); 50 } 51 for(int i=1;i<=m;i++){ 52 int x; 53 scanf("%d",&x); 54 mp[x]=true; 55 } 56 57 for(int len=1;len<=n;len++){ 58 for(int j=1;j<=n-len;j++){ 59 int i=j+len; 60 if(mp.count(a[i]-a[j])&&dp[i-1][j+1]){ 61 dp[i][j]=true; 62 continue; 63 } 64 for(int k=j+1;k<i;k++){ 65 if(dp[i][k]&&dp[k-1][j]){ 66 dp[i][j]=true; 67 break; 68 } 69 else if(2*a[k]==a[i]+a[j]&&dp[i-1][k+1]&&dp[k-1][j+1]&&mp.count(a[i]-a[k])){ 70 dp[i][j]=true; 71 break; 72 } 73 } 74 } 75 } 76 for(int i=1;i<=n;i++){ 77 d[i]=max(d[i],d[i-1]); 78 for(int j=i-1;j>=1;j--){ 79 if(dp[i][j]) 80 d[i]=max(d[i],d[j-1]+i-j+1); 81 } 82 } 83 printf("%d\n",d[n]); 84 } 85 return 0; 86 }
1005 dfs序+线段树区间最大值
没有AC。。。。。