一、1.简单计算 我们要求∑iq/p (i∈【0，p】) 注意这里是下取整。
然后我们发现数据很大，1e9，并且数据组数t是1e6的，所以我们的算法应该是O（1）的或者O（logn）的。这里提供两种思路：
①考虑下取整的性质接拆式子。∑iq/p=∑（iq-iq%p）/p。然后我们可以先求出∑（iq-iq%p），我们发现第一个iq是一个等差数列。然后如果p与q互质，那么iq%p应该是从0~p-1各出现一次。所以这也是一个等差数列，可以直接O（1）求。如果p与q不互质，从样例我们容易发现，如果gcd（p，q）=d，他正好是把p/d之后的p',0~p'-1各出现了d次。所以继续等差数列求就可以。
#include<bits/stdc++.h> #define ll long long using namespace std; ll t,p,q,m; ll gcd(ll a,ll b){ return b==0 ? a : gcd(b,a%b); } int main(){ freopen("simplecalc.in","r",stdin); freopen("simplecalc.out","w",stdout); scanf("%lld",&t); while(t--){ scanf("%lld%lld",&p,&q); ll d=gcd(p,q); ll temp=(q*(p+1)-d*(p/d-1))/2; printf("%lld\n",temp); } return 0; }②我们发现∑iq/p=∑（p-i）*q/p，如果我们可以合理的把右式拆开，就可以把前后两个削去，计算应该会变得比较容易。所以我们求2∑iq/p=∑iq/p+∑（p-i）*q/p。我们假设个x，y，x= p*m1+r1，y=p*m2+r2,（x-y）/p和x/p-y/p相等的情况是r1>r2，否则我们需要多减去一个1。x在题中其实是p*q，所以他的r1是0，所以只要i*q不是p的整数倍，我们就多减1.所以我们求得的答案应该是p*（p+1）-p+p*q/lcm（p，q）=p*（p+1）-p+gcd( p , q )最后再除以2.
二、大致题意：给了你n个硬盘，每个硬盘首先需要占用一个容量a来格式化，然后它会再提供一个b容量。如果在你格式化的时候容量不足a，就需要额外的容量。求你按照最优的顺序把n个硬盘全部格式化之后所需的额外容量输出。
容易发现，每个硬盘的选取顺序与它对容量的贡献有关。我们发现硬盘只有两种，一个是格式化之后对剩余总容量做正贡献，一个是负贡献。我们把正贡献的分成一类，负贡献的放在一起。肯定是先取完正贡献再取负贡献的更优。然后具体要做的是考虑如何选取这两类分别选时的顺序。贪心策略是，对正贡献的硬盘按照a从小到大排序，从小向大取一定更优。对于负贡献，按b从大到小排序，从大到小取一定更优。
#include<bits/stdc++.h> #define ll long long using namespace std; int n,num1,num2;ll ans; struct node{ ll x,y; }a[1001000],b[1001000]; bool cmp(node c,node d){ return c.x<d.x; } bool cmps(node c,node d){ return c.y>d.y; } int main(){ freopen("reformat.in","r",stdin); freopen("reformat.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ ll x,y;scanf("%lld%lld",&x,&y); if(y-x>0) a[++num1].x=x,a[num1].y=y; else b[++num2].x=x,b[num2].y=y; } sort(a+1,a+num1+1,cmp); sort(b+1,b+num2+1,cmps); ll now=0; for(int i=1;i<=num1;i++){ now-=a[i].x;if(now<0) ans-=now,now=0; now+=a[i].y; } for(int i=1;i<=num2;i++){ now-=b[i].x;if(now<0) ans-=now,now=0; now+=b[i].y; } printf("%lld\n",ans); return 0; }三、题意：
有n个人，每个人只会说三种话，一种是说自己右边的人说假话，一种是说自己右边的人说真话，一种是说n个人当中有k个人说真话，其他的全是假话。我们只需要判断有没有一种情况是成立的，如果所有的人都互相矛盾，输出inconsistent，否则输出consistent。
看上去貌似很不可做，其实就是一道大模拟。假设说第三种话的有s个人，其实这个环被这s个人隔开。对于每一个说第三种话的人，它向左一直走，直到另一个说第三种话的人，这一段中人说真假话我们都可以确定了。所以我们可以枚举每一个s的真假，然后O（n）判断是否冲突就可以。这样复杂度是O（k*n）的，但是我们可以提前O（n）预处理一下，然后枚举一个s，再分别枚举其他的s，通过预处理的结果判断是否冲突。复杂度就是O（n+k^2）。
#include<bits/stdc++.h> using namespace std; inline char getc() { char ch; while(isspace(ch=getchar())) ; return ch; } inline int getint() { char ch; while(!isdigit(ch=getchar())) ; int x=ch-'0'; while(isdigit(ch=getchar())) x=x*10+ch-'0'; return x; } const int N=100010; struct block { int s,num,len,t[2],f[2]; }p[N]={}; bool block_cmp(const block &b1,const block &b2) { return b1.num<b2.num; } int n,m,a[N]={},b[N]={}; char ans[N]={}; void init() { fill(p+1,p+m+1,(block){0,0,0,{0,0},{0,0}}); m=0; fill(a+1,a+n+1,0),fill(b+1,b+n+1,0); fill(ans+1,ans+n+1,'\0'); n=getint(); for(int i=1;i<=n;++i) { char ch=getc(); if(ch=='+') a[i]=1; if(ch=='-') a[i]=2; if(ch=='$') b[i]=getint(); } } void get_block(int now) { ++m; p[m].s=now; int next=1; while(a[now]) { p[m].t[0]+=next==1; next= next==1 ? a[now] : 3-a[now]; now= now%n+1; ++p[m].len; } p[m].num=b[now]; p[m].f[0]=next; p[m].t[1]=p[m].len-p[m].t[0]; p[m].f[1]=3-p[m].f[0]; } void mark(int now,int next) { while(a[now]) { ans[now]= next==1 ? 't' : 'f'; next=next== 1 ? a[now] : 3-a[now]; now=now%n+1; } ans[now]=next==1 ? 't' : 'f'; } void work() { for(int i=1;i<=n;++i) if(a[i]==0) get_block(i%n+1); if(m==0) { int next=1,con=next==a[1] ? 1 : 2; ans[1]='t'; repeat: for(int i=2;i<=n;++i) { ans[i]=next==1 ? 't' : 'f'; next= (next==1) ? a[i] : 3-a[i]; } if(next!=con) { if(ans[1]=='f') puts("inconsistent"); else { ans[1]='f'; next=2; con= next==a[1] ? 1 : 2; goto repeat; } } else { ans[1]= next==2 ? 'f' : 't'; puts("consistent"); //puts(ans+1); } } else { sort(p+1,p+m+1,block_cmp); int t=0; for(int i=1;i<=m;++i) t+=p[i].f[0]==2 ? p[i].t[0] : p[i].t[1]; bool flag=true; for(int i=1;i<=m && flag;++i) if(t==p[i].num) flag=false; if(flag) { puts("consistent");/* for(int i=1;i<=m;++i) mark(p[i].s,p[i].f[0]==2 ? 1 : 2); puts(ans+1);*/ } for(int i=1,r=1;i<=m && !flag;i=r) { while(r<=m && p[r].num==p[i].num) ++r; for(int j=i;j<r;++j) { t+=p[j].f[0]==1 ? p[j].t[0] : p[j].t[1]; t-=p[j].f[0]==2 ? p[j].t[0] : p[j].t[1]; } if(t+r-i==p[i].num) { puts("consistent");/* for(int j=1;j<=m;++j) if(i<=j && j<r) mark(p[j].s,p[j].f[0]==1 ? 1 : 2); else mark(p[j].s,p[j].f[0]==2 ? 1 : 2); for(int j=1;j<=n;++j) putchar(ans[j]); putchar('\n');*/ flag=true; } for(int j=i;j<r;++j) { t-=p[j].f[0]==1 ? p[j].t[0] : p[j].t[1]; t+=p[j].f[0]==2 ? p[j].t[0] : p[j].t[1]; } } if(!flag) puts("inconsistent"); } } int main() { freopen("truth.in","r",stdin); freopen("truth.out","w",stdout); int T=getint(); while(T--) { init(); work(); } fclose(stdin); fclose(stdout); return 0; }
