Clockwise or Counterclockwise
题目大意:
给你三个点ABC，判断A->B->C的方向（逆时针或者顺时针）
思路:
叉积
/*
A（x1,y1) B(x2,y2) C(x3,y3)
向量AB=（x2-x1,y2-y1)
向量AC=（x3-x1,y3-y1）
若 AB x AC < 0 则 ABC 顺时针
若 AB x AC > 0 则 ABC 逆时针
若 AB x AC = 0 则 AB、AC 共线 同向或者反向
*/
struct node{
double x,y;
}a[N];
double cross(node a,node b,node c){//>0，ab在ac顺时针；<0，ab在ac逆时针
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
AC Code:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=4;
struct node{
double x,y;
}a[N];
double cross(node a,node b,node c){//>0，ab在ac顺时针；<0，ab在ac逆时针
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
void solve(){
cin>>a[1].x>>a[1].y>>a[2].x>>a[2].y>>a[3].x>>a[3].y;
double d=cross(a[1], a[2], a[3]);
if(d<0) cout<<"Clockwise"<<endl;
else cout<<"Counterclockwise"<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
int T;
cin>>T;
while(T--) solve();
return 0;
}
Fluctuation Limit
题目大意:
给你n个区间l和r，以及波动k
求是否有一个序列满足在l~r（可以波动k）
思路:
官方题解：
如果 i 是在 [l,r] 范围内, 那么 i + 1 必须要在 [l−k,r + k] 范围内．这是因为如果 i + 1 选了 范围外的值, i 就无解了． 这样可以从左往右, 把左边的约束带到右边．再从右往左做一遍．最后剩下的区间应该就是可 行域．因为题目只要求一种方案, 全部选最低的即可．复杂度 O(n)．
AC Code:
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n, k;
int l[N], r[N], L, R;
void solve(){
cin>>n>>k;
l[0]=0, r[0]=INF;
for(int i=1; i<=n; i++){
cin>>L>>R;
l[i]=max(l[i-1]-k, L);
r[i]=min(r[i-1]+k, R);
}
int flag=1;
for(int i=n-1; i>=1; i--){
l[i]=max(l[i+1]-k, l[i]);
r[i]=min(r[i+1]+k, r[i]);
if(l[i]>r[i]) flag=0;
}
if(flag){
cout<<"YES"<<endl;
for(int i=1; i<=n; i++) cout<<l[i]<<" ";
cout<<endl;
}
else cout<<"NO"<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
int T;
cin>>T;
while(T--) solve();
return 0;
}
Isomorphic Strings（哈希）
题目大意:
给一个字符串 s ，长度为 n ，问是否存在一个 k ，满足 k∣n ，将 s 分成相等的 k 段子串，每一段子串互为循环同构。
思路:
主要是求得第一个子串的所有循环同构的哈希值集合，若第一个集合为第二个的子集，就合法
AC Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e7 +7;
const int N=5e6+6;
const int maxn=2e7;
const int base=1543;
int T, n;
char s[N];
int Hash[N],por[N];
int id[maxn],cnt;
void init(){ //初始化por数组
por[0]=1;
for(int i=1;i<N;i++) por[i]=1LL*por[i-1]*base%mod;
}
void get_hash(int len, char s[]){ //哈希处理总的长度的字符串
for(int i=1;i<=len;i++)
Hash[i]=(1LL*Hash[i-1]*base%mod+(s[i]-'a'+1))%mod;
}
int js(int l, int r){ //子串的哈希值
return (Hash[r]-1LL*Hash[l-1]*por[r-l+1]%mod+mod)%mod;
}
bool solve(int d,int cnt)
{
if(d==1) return 0;
int len=n/d;
int l=1, r=len;
int tmp=js(l,r);
id[tmp]=cnt;
for(int i=1;i<len;i++){ //同构的其它串的hash值
tmp=(1LL*js(i+1,len)*por[i]%mod +js(1,i))%mod;
id[tmp]=cnt;
}
for(int i=1;i<=d;i++){ //判断后面的子串是否合法
int x=js(l,r);
if(id[x]!=cnt) return 0;
l+=len, r+=len;
}
return 1;
}
int main()
{
init();
scanf("%d",&T);
cnt=0;
while(T--)
{
scanf("%d",&n);
scanf("%s",s+1);
get_hash(n, s);
int flag=0;
for(int i=1;i*i<=n && !flag;i++)//枚举段数
{
if(n%i==0){
flag|=solve(i,++cnt);
flag|=solve(n/i,++cnt);
}
}
if(flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}
Comments | NOTHING