1006
倒着维护区间之间的约束关系，再正向维护一边，剩下的区间就是答案的可行域，我们只需要把每个区间的可行域的(l)输出即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
#define PII pair <ll,ll>
#define fr first
#define sc second
#define mp make_pair
const int N=1e5+7;
PII a[N],b[N];
int main(){
int T=input();
while(T--){
int n=input(),k=input();
for(int i=1;i<=n;i++){
a[i].fr=input(),a[i].sc=input();
b[i].fr=b[i].sc=0;
}
int flag=1;
b[n]=a[n];
for(int i=n-1;i>=1&&flag;i--){
ll l=b[i+1].fr-k,r=b[i+1].sc+k;
if(a[i].fr>r||a[i].sc<l){
flag=0;
break;
}else{
b[i].fr=max(l,a[i].fr);
b[i].sc=min(r,a[i].sc);
}
}
for(int i=2;i<=n&&flag;i++){
ll l=b[i-1].fr-k,r=b[i-1].sc+k;
if(b[i].fr>r||b[i].sc<l){
flag=0;
break;
}else{
b[i].fr=max(l,b[i].fr);
b[i].sc=min(r,b[i].sc);
}
}
if(flag){
printf("YES
");
for(int i=1;i<=n;i++) printf("%d%c",b[i].fr,i==n? '
':' ');
}else printf("NO
");
}
}
1008
构造题，分别构造六个方向的边，从外向内螺旋构造即可，大六边形层数奇偶不同时最内层构造方法不同需要特判。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=2e6+7;
char Ans[N];
int top=0;
void Edge(int x,int y){
for(int i=1;i<=x-2;i++){
Ans[top++]='0'+(4+y-1)%6+1;
Ans[top++]='0'+(2+y-1)%6+1;
}
Ans[top++]='0'+(3+y-1)%6+1;
}
void circle(int x){
for(int i=0;i<6;i++) Edge(x,i);
Ans[top-3]='2',Ans[top-2]='4',Ans[top-1]='3';
}
int main(){
int T=input();
while(T--){
memset(Ans,' ',sizeof(Ans));
top=0;
int n=input();
if(n%2==1){
for(int i=n;i>=2;i-=2) circle(i);
}else{
for(int i=n;i>=3;i-=2) circle(i);
for(int i=5;i>=1;i--) Ans[top++]='0'+i;
Ans[top]='5';
}
printf("%s
",Ans);
}
}
1009
对于此题我们考虑使用哈希来过，但是直接哈希显然会超时，此时我们需要考虑一个重要的剪枝，我们假设当前有(k)个子串，那么显然(k)不能超过所有字符个数的最大公约数，并且可行的(k)的取值一定是所有字符最大公约数的约数。那么我们可以利用这个性质剪枝，使得在我们期望的时限中通过本题。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=5e6+7;
char s[N];
int n;
ll base[3]={19260817,(int)1e5+7,244781};
ll mod[3]={(int)1e9+7,998244353,(int)1e7+7};
ll p[3][N],h[3][N];
void init(){
p[0][0]=p[1][0]=p[2][0]=1;
for(int i=1;i<N;i++){
p[0][i]=p[0][i-1]*base[0]%mod[0];
p[1][i]=p[1][i-1]*base[1]%mod[1];
p[2][i]=p[2][i-1]*base[2]%mod[2];
}
}
inline ll Hsh(int l,int r,int id){
return ((h[id][r]-h[id][l-1]*p[id][r-l+1])%mod[id]+mod[id])%mod[id];
}
const ll M=1e7+7;
ll tmp[M];
inline ll hhsh(ll a,ll b,ll c){
ll res=0;
res=(res*base[0]+a)%M;
res=(res*base[0]+b)%M;
res=(res*base[0]+c)%M;
return res;
}
int f=0;
inline bool check(int k){
f++;
for(int i=0;i<k;i++){
ll a=(Hsh(i+1,k,0)*p[0][i]%mod[0]+Hsh(1,i,0))%mod[0];
ll b=(Hsh(i+1,k,1)*p[1][i]%mod[1]+Hsh(1,i,1))%mod[1];
ll c=(Hsh(i+1,k,2)*p[2][i]%mod[2]+Hsh(1,i,2))%mod[2];
ll key=hhsh(a,b,c);
tmp[key]=f;
}
for(int i=1;i<=n;i+=k){
ll a=Hsh(i,i+k-1,0);
ll b=Hsh(i,i+k-1,1);
ll c=Hsh(i,i+k-1,2);
ll key=hhsh(a,b,c);
if(tmp[key]!=f) return 0;
}
return 1;
}
ll cnt[26];
int main(){
init();
int T=input();
while(T--){
n=input();
scanf("%s",s+1);
if(n==1){printf("No
");continue;}
memset(cnt,0,sizeof cnt);
h[0][0]=h[1][0]=h[1][0]=0;
for(int i=1;i<=n;i++){
cnt[s[i]-'a']++;
h[0][i]=(h[0][i-1]*base[0]+s[i])%mod[0];
h[1][i]=(h[1][i-1]*base[1]+s[i])%mod[1];
h[2][i]=(h[2][i-1]*base[2]+s[i])%mod[2];
}
ll gd=0;
for(int i=0;i<26;i++) gd=__gcd(gd,cnt[i]);
if(gd==1){
printf("No
");
continue;
}
int flag=0;
flag|=check(n/gd);
for(ll k=2;k*k<=gd&&!flag;k++){
if(gd%k==0){
flag|=check(n/k);
if(k==gd/k) continue;
flag|=check(n/(gd/k));
}
}
if(flag) printf("Yes
");
else printf("No
");
}
}
1003
温暖的签到题。拿叉积随便搞搞就过了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
#define PII pair <double,double>
#define fr first
#define sc second
#define mp make_pair
const int N=7;
PII a[N];
int n;
double poly(){
double area=0;
for(int i=0,j;i<n;i++){
j=(i+1)%n;
area+=a[i].fr*a[j].sc;
area-=a[i].sc*a[j].fr;
}
area/=2.0;
return area;
}
int main(){
int T=input();
while(T--){
n=3;
for(int i=0;i<3;i++){
scanf("%lf%lf",&a[i].fr,&a[i].sc);
}
if(poly()<0) printf("Clockwise
");
else printf("Counterclockwise
");
}
}