本文主要是介绍xdoj(1187~1195 )Orz熊猫杯。,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这个月好多事啊马上四级,ccf,选修的大作业,两次数据结构上机报告,物理实验考试,以及这个月过去的马上就到了期末考试了。usaco暂时有空就刷没空就不刷了。
上个星期日学校Oj上搞了一个比赛Orz熊猫杯比赛时只做出来三道题,然后题解出来了就开始照着题解补题补得我心累。(虽然没什么参加只有20个人)。
还有一道题1191,还没搞出来我觉得我的想法没错啊(补:思路果然没错vector没有初始化所以一直wa),在Oj上也跑了800多毫秒可是就是答案错了。再想想想不出来就问我们班大佬了Orz.
xdoj 1187这道题时限是10s我原本以为签到题然后就没有然后了。补这道题也花了我超长时间。结果是最后除以2取模没用数论倒数。。。。
官方题解在最下面
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
#define N 100005
ll temp1,temp2;
const ll a=500000004;
const ll mod=1e9+7;
ll sum1[N*4];
ll sum2[N*4];
ll add1[N*4];
ll add2[N*4];
void pushup(int rt)
{sum1[rt]=(sum1[rt<<1]+sum1[rt<<1|1])%mod;sum2[rt]=(sum2[rt<<1]+sum2[rt<<1|1])%mod;
}
void pushdown(int rt,int m)
{if(add2[rt]){add2[rt<<1]=(add2[rt<<1]+add2[rt])%mod;add2[rt<<1|1]=(add2[rt<<1|1]+add2[rt])%mod;sum2[rt<<1]=(sum2[rt<<1]+((m-(m>>1))*add2[rt])%mod*add2[rt]+2*sum1[rt<<1]*add2[rt])%mod;sum2[rt<<1|1]=(sum2[rt<<1|1]+((m>>1)*add2[rt])%mod*add2[rt]+2*sum1[rt<<1|1]*add2[rt])%mod;add2[rt]=0;}if(add1[rt]){add1[rt<<1]=(add1[rt<<1]+add1[rt])%mod;add1[rt<<1|1]=(add1[rt<<1|1]+add1[rt])%mod;sum1[rt<<1]=(sum1[rt<<1]+(m-(m>>1))*add1[rt])%mod;sum1[rt<<1|1]=(sum1[rt<<1|1]+(m>>1)*add1[rt])%mod;add1[rt]=0;}
}
void update(int L,int R,ll c,int l,int r,int rt)
{if(l>=L&&r<=R){add1[rt]=(add1[rt]+c)%mod;add2[rt]=(add2[rt]+c)%mod;sum2[rt]=(sum2[rt]+(ll)((r-l+1)*c)%mod*c+2*sum1[rt]*c)%mod;sum1[rt]=(sum1[rt]+(ll)(r-l+1)*c)%mod;return;}pushdown(rt,r-l+1);int m=(l+r)>>1;if(L<=m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); pushup(rt);
}
void Query(int L,int R,int l,int r,int rt)
{ if(L<=l&&R>=r) { temp1=(temp1+sum1[rt])%mod; temp2=(temp2+sum2[rt])%mod;return;}pushdown(rt,r-l+1); int m=(l+r)>>1; if(L<=m) Query(L,R,lson); if(R>m) Query(L,R,rson); return ;
}
int main()
{int n,m;int l,r,q;ll c;while(~scanf("%d %d",&n,&m)){memset(sum1,0,sizeof(sum1));memset(sum2,0,sizeof(sum2));memset(add1,0,sizeof(add1));memset(add2,0,sizeof(add2));while(m--){temp1=0,temp2=0;scanf("%d",&q);if(q==1){scanf("%d %d %lld",&l,&r,&c);update(l,r,c,1,n,1);}if(q==2){scanf("%d %d",&l,&r);Query(l,r,1,n,1);long long ans=(((temp1*temp1-temp2+mod)%mod)*a)%mod;printf("%lld\n",ans);}}}
}
xdoj 1188
现学现做==
#include<bits/stdc++.h>
using namespace std;
int c[510];
int a[510];
typedef long long ll;
const ll mod=1e9+7;
ll q[50005];
ll dp[10010];
int head,tail;
int main()
{int k,l,r;while(~scanf("%d %d %d",&k,&l,&r)){ll sum=0;memset(dp,0,sizeof(dp));dp[0]=1;for(int i=1;i<=k;i++){scanf("%d %d",&c[i],&a[i]);if(r/c[i]<a[i]) a[i]=r/c[i];for(int d=0;d<c[i];d++){head=0,tail=0;sum=0;for(int j=0;j<=(r-d)/c[i];j++){q[++head]=dp[j*c[i]+d];sum=(sum+q[head])%mod;if(head>(a[i]+tail+1)){tail++;sum=(sum-q[tail]+mod)%mod;}dp[j*c[i]+d]=sum;} }}ll ans=0;for(int i=l;i<=r;i++)ans=(ans+dp[i])%mod;printf("%lld\n",ans);}
}
xdoj 1189
这道题一开始没预处理总是超时最后预处理一大批很大的数字总算过了
#include<bits/stdc++.h>
using namespace std;
long long f[9000000];
void init()
{long long sum=0;for(long long i=1;i<=3000;i++){for(long long j=i*i;j<=9000000;j+=i*i)f[j]++;}for(int i=1;i<=9000000;i++)f[i]=f[i]+f[i-1];
}
void fu(long long n)
{long long sum=0;for(long long i=3000;i<=sqrt(n);i++){for(long long j=i*i;j<=n;j+=i*i)sum++;}printf("%lld\n",sum+f[9000000]);
}
int main()
{long long n;init();while(scanf("%lld",&n)!=EOF){if(n<=9000000)printf("%lld\n",f[n]);else{fu(n);}}}
xdoj 1190
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll pow(ll a,ll b,ll p)
{ll ans=1;while(b){if(b&1) ans=ans*a%p;b>>=1;a=a*a%p;}return ans;
}
int main()
{ll a,b,k;while(scanf("%lld %lld %lld",&a,&b,&k)!=EOF){ll res=pow(a,b,k-1);if(res==0)res=k-1;ll ans=(((pow(a,b,mod)-res+mod)%mod)*pow(k-1,mod-2,mod))%mod;printf("%lld\n",ans);}
}
xdoj 1191待补
#include<bits/stdc++.h>
using namespace std;
long long a[100010];
bool vis[100010];
vector<int> g[100010];
int mark;
struct node
{int num;long long sum;
}b,d;
long long ans;
queue<node>q;
void bfs2(int k)
{memset(vis,0,sizeof(vis));b.num=k;b.sum=a[k];q.push(b);ans=a[k];vis[k]=1;while(!q.empty()){b=q.front();int u=b.num;q.pop();for(int i=0;i<g[u].size();i++){int v=g[u][i];if(!vis[v]){d.num=v;d.sum=b.sum+a[v];q.push(d);if(ans<d.sum){ans=d.sum;}vis[v]=1;}}}printf("%lld\n",ans);
}
void bfs1(int k)
{memset(vis,0,sizeof(vis));b.num=k;b.sum=a[k];q.push(b);ans=a[k];vis[k]=1;mark=k;while(!q.empty()){b=q.front();int u=b.num;q.pop();for(int i=0;i<g[u].size();i++){int v=g[u][i];if(!vis[v]){d.num=v;d.sum=b.sum+a[v];q.push(d);if(ans<d.sum){ans=d.sum;mark=v;}vis[v]=1;}}}
}int main()
{int n,m;int u,v,flag;long long l,r;while(~scanf("%d",&n)){memset(g,0,sizeof(g));memset(a,0,sizeof(a));for(int i=1;i<=n-1;i++){scanf("%d %d",&u,&v);g[u].push_back(v);g[v].push_back(u);}scanf("%d",&m);int temp=0;for(int i=1;i<=m;i++){scanf("%lld%lld",&l,&r);a[l]=r;} bfs1(1);bfs2(mark);}
}
xdoj 1192
#include<bits/stdc++.h>
using namespace std;
char s[50];
char s1[50],s2[50],s3[50];
typedef long long ll;
ll gcd(ll a,ll b)
{ return b==0?a:gcd(b,a%b);
}
ll num(char a[])
{ll ans=0;for(int i=0;i<strlen(a);i++)ans=ans*10+a[i]-'0';return ans;
}
int main()
{while(~scanf("%s",s)){if (sscanf(s, "%[0-9].%[0-9]_%[0-9]...", s1,s2,s3)==3) {int l=strlen(s3);ll t1=0,t2=0,t3=0;t3=num(s3);ll p=pow(10,l)-1;t1=num(s1);t2=num(s2);int r=strlen(s2);ll t4=pow(10,r);ll q=t1*p*t4+t2*p+t3;p=p*t4;ll temp=gcd(q,p);printf("%lld/%lld\n",q/temp,p/temp);} else if (sscanf(s, "%[0-9]._%[0-9]...", s1,s2)==2) {ll t1=0,t2=0;t1=num(s1);t2=num(s2);int l=strlen(s2);ll p=pow(10,l)-1;ll t3=pow(10,l);ll q=t1*p+t2;ll temp=gcd(q,p);printf("%lld/%lld\n",q/temp,p/temp);} else if(sscanf(s,"%[0-9].%[0-9]",s1,s2)==2){ll t1,t2;int l=strlen(s2);t1=num(s1);t2=num(s2);ll p=pow(10,l);ll q=t1*p+t2;ll temp=gcd(q,p);printf("%lld/%lld\n",q/temp,p/temp); }else if(sscanf(s,"%[0-9]",s1)==1){ll t=num(s1);printf("%lld/1\n",t);}}
}
xdoj 1193
#include<bits/stdc++.h>
using namespace std;
int a[100010];
long long b[100010];
int main()
{int n;while(~scanf("%d",&n)){int cnt=0;for(int i=1;i<=n;i++)scanf("%d",&a[i]);int l=1,r=n;b[l]=a[l];b[r]=a[r];while(l<r){long long t1=b[l],t2=b[r];if(t1==t2){cnt+=2;l++;r--;b[l]=a[l];b[r]=a[r];}else if(t1>t2){r--;b[r]=b[r+1]+a[r];}else if(t1<t2){l++;b[l]=a[l]+b[l-1];}}if(l==r)cnt++;printf("%d\n",cnt);}
}
xdoj 1194
#include<bits/stdc++.h>
using namespace std;
char s[1005];
int main()
{while(~scanf("%s",s)){int len=strlen(s);if(len!=1){printf("%d 10\n",len-1);printf("%c",s[len-1]);for(int i=len-2;i>=0;i--){printf(" %c",s[i]);}printf("\n");}else{if(s[0]=='1'){printf("1 1\n");printf("1 0\n");}else{printf("%d 1\n",s[0]-'0'-1);printf("1");for(int i=1;i<s[0]-'0';i++)printf(" 1");printf("\n");}}}
}
xdoj 1195
#include<bits/stdc++.h>
using namespace std;
int a[20010];
int b[20010];
int main()
{int n,m,x;while(~scanf("%d%d%d",&n,&m,&x)){int cnt=0;int ans=0;int e,d;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=m;i++){scanf("%d",&b[i]);}sort(a+1,a+n+1);sort(b+1,b+n+1);int l=1,r=1;while(l<=n&&r<=m){int t1=a[l],t2=b[r];if(t1-t2>0){if(t1-t2>x)r++;else {cnt++;l++;r++;}}else {if(abs(t1-t2)>x){l++;}else{cnt++;l++;r++;}}}printf("%d\n",cnt);}
}
官方题解PDF
这篇关于xdoj(1187~1195 )Orz熊猫杯。的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!