目录
1001鸡爪
对于大于3的一定是以1，2，3点为鸡爪的另外三个点，对于以1，2，3为中心的稍微贪心下就行
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 2e5;
const int qwq = 303030;
const int inf = 0x3f3f3f3f;
int n;
string str;
void solve(){
cin>>n;
int sum =0 ;
int m = n /3 ;
if(m==0) {
for (int i = 2; i <= n + 1; i++)
cout << 1 << ' ' << i << '\n';
return;
}
for(int i=1;i<=min(3,m);i++){
if(i==1) {
for (int j = i + 1; j <= m + 3 + (n % 3); j++) {
cout << i << ' ' << j << '\n';
}
}else {
for (int j = i + 1; j <= m + 4 - i; j++) {
cout << i << ' ' << j << '\n';
}
}
}
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
cin >> T ;
while(T--)solve();
return 0;
}
1003绝对不模拟的简单魔方
6个面，每个2种方向，转三次就是12*12*12种情况，记录8个点的情况，暴力
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct jiao {
int n1,n2,n3;
} j[10],j2[10];
int mp[20][20],f=1,ans0[4];
char s[20];
void swp(jiao a,jiao &b,int x){
if(x==1){
b.n1=a.n2;
b.n2=a.n3;
b.n3=a.n1;
return;
}
if(x==2){
b.n1=a.n3;
b.n2=a.n1;
b.n3=a.n2;
return;
}
if(x==3){
b.n1=a.n3;
b.n2=a.n2;
b.n3=a.n1;
return;
}
if(x==4){
b.n1=a.n2;
b.n2=a.n1;
b.n3=a.n3;
return;
}
}
void z(int x){
jiao t;
if(x==1) t=j2[1],j2[1]=j2[3],j2[3]=j2[4],j2[4]=j2[2],j2[2]=t;
if(x==2) t=j2[1],j2[1]=j2[2],j2[2]=j2[4],j2[4]=j2[3],j2[3]=t;
if(x==3) t=j2[5],j2[5]=j2[7],j2[7]=j2[8],j2[8]=j2[6],j2[6]=t;
if(x==4) t=j2[5],j2[5]=j2[6],j2[6]=j2[8],j2[8]=j2[7],j2[7]=t;
if(x==5){
t=j2[3];
swp(j2[5],j2[3],4);
swp(j2[6],j2[5],2);
swp(j2[4],j2[6],3);
swp(t,j2[4],1);
}
if(x==6){
t=j2[3];
swp(j2[4],j2[3],2);
swp(j2[6],j2[4],3);
swp(j2[5],j2[6],1);
swp(t,j2[5],4);
}
if(x==7){
t=j2[2];
swp(j2[1],j2[2],2);
swp(j2[7],j2[1],3);
swp(j2[8],j2[7],1);
swp(t,j2[8],4);
}
if(x==8){
t=j2[2];
swp(j2[8],j2[2],4);
swp(j2[7],j2[8],2);
swp(j2[1],j2[7],3);
swp(t,j2[1],1);
}
if(x==9){
t=j2[2];
swp(j2[4],j2[2],1);
swp(j2[6],j2[4],4);
swp(j2[8],j2[6],2);
swp(t,j2[8],3);
}
if(x==10){
t=j2[2];
swp(j2[8],j2[2],3);
swp(j2[6],j2[8],1);
swp(j2[4],j2[6],4);
swp(t,j2[4],2);
}
if(x==11){
t=j2[1];
swp(j2[3],j2[1],2);
swp(j2[5],j2[3],3);
swp(j2[7],j2[5],1);
swp(t,j2[7],4);
}
if(x==12){
t=j2[1];
swp(j2[7],j2[1],4);
swp(j2[5],j2[7],2);
swp(j2[3],j2[5],3);
swp(t,j2[3],1);
}
}
void check() {
int an=0,f1=1;
for(int i=1; i<=8; i++) {
f1=0;
if(j[i].n1!=j2[i].n1) an++,f1=1;
if(j[i].n2!=j2[i].n2) an++,f1=1;
if(j[i].n3!=j2[i].n3) an++,f1=1;
if(f1) {
ans0[1]=j[i].n1;
ans0[2]=j[i].n2;
ans0[3]=j[i].n3;
}
if(an>=3) {
f=3;
return;
}
}
if(an==0) f=0;
if(an==2) f=2;
}
void solve() {
f=1;
j2[1].n1=1,j2[1].n2=5,j2[1].n3=2;
j2[2].n1=1,j2[2].n2=4,j2[2].n3=5;
j2[3].n1=1,j2[3].n2=2,j2[3].n3=3;
j2[4].n1=1,j2[4].n2=3,j2[4].n3=4;
j2[5].n1=6,j2[5].n2=2,j2[5].n3=3;
j2[6].n1=6,j2[6].n2=3,j2[6].n3=4;
j2[7].n1=6,j2[7].n2=5,j2[7].n3=2;
j2[8].n1=6,j2[8].n2=4,j2[8].n3=5;
for(int i=1; i<=9; i++) {
cin>>s;
for(int k=1; k<=12; k++) {
if(s[k-1]<='9'&&s[k-1]>='1') mp[i][k]=s[k-1]-'0';
}
}
j[1].n1=mp[1][4],j[1].n2=mp[4][12],j[1].n3=mp[4][1];
j[2].n1=mp[1][6],j[2].n2=mp[4][9],j[2].n3=mp[4][10];
j[3].n1=mp[3][4],j[3].n2=mp[4][3],j[3].n3=mp[4][4];
j[4].n1=mp[3][6],j[4].n2=mp[4][6],j[4].n3=mp[4][7];
j[5].n1=mp[7][4],j[5].n2=mp[6][3],j[5].n3=mp[6][4];
j[6].n1=mp[7][6],j[6].n2=mp[6][6],j[6].n3=mp[6][7];
j[7].n1=mp[9][4],j[7].n2=mp[6][12],j[7].n3=mp[6][1];
j[8].n1=mp[9][6],j[8].n2=mp[6][9],j[8].n3=mp[6][10];
check();
if(!f) {
cout<<"No problem"<<'\n';
} else if(f==2) {
sort(ans0+1,ans0+4);
cout<<ans0[1]<<' '<<ans0[2]<<' '<<ans0[3]<<'\n';
} else {
for(int i=1; i<=12; i++) {
f=1;
z(i);
check();
if(f<=2) break;
for(int k=1; k<=12; k++) {
f=1;
z(k);
check();
if(f<=2) break;
for(int l=1; l<=12; l++) {
f=1;
z(l);
check();
if(f<=2){
break;
}
if(l%2==0) z(l-1);
else z(l+1);
}
if(f<=2){
break;
}
if(k%2==0) z(k-1);
else z(k+1);
}
if(f<=2){
break;
}
if(i%2==0) z(i-1);
else z(i+1);
}
if(!f) {
cout<<"No problem"<<'\n';
} else if(f==2) {
sort(ans0+1,ans0+4);
cout<<ans0[1]<<' '<<ans0[2]<<' '<<ans0[3]<<'\n';
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _ = 1;
cin >> _;
while (_--) solve();
return 0;
}1006传奇勇士小凯
每个点的贡献其实就是倒数，求倒数和最长的一条链的大小
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e5+100;
vector<int>to[N];
int a[N];
int b[N];
int res=1;
void dfs(int u,int fa){
for(auto v:to[u]){
if(v==fa)continue;
b[v]=b[u]+15*res/a[v];
dfs(v,u);
}
}
void solve(){
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
to[u].push_back(v);
to[v].push_back(u);
}
for(int i=1;i<=n;i++){
cin>>a[i];
}
b[1]=15*res/a[1];
dfs(1,-1);
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,b[i]);
}
int g=__gcd(ans,res);
cout<<ans/g<<"/"<<res/g<<'\n';
for(int i=1;i<=n;i++)to[i].clear();
}
signed main() {
for(int i=1;i<=15;i++){
res*=i;
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _ = 1;
cin >> _;
while (_--) solve();
return 0;
}1007URL划分
根据题意即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
void solve(){
string s,ss;
cin>>s;
int l=0;
for(int i=0;i<s.size();i++){
if(s[i]==':'){
ss=s.substr(l,i-l);
cout<<ss<<'\n';
l=i+3;
}
}
int ff=0;
for(int i=l;i<=s.size();i++){
if(s[i]=='/'){
ss=s.substr(l,i-l);
l=i+1;
if(ss.find('=')!=-1||ff==0){
cout<<ss<<'\n';
ff=1;
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _ = 1;
cin >> _;
while (_--) solve();
return 0;
}1008成长，生命，幸福
每个点在拓展m次之后的贡献为， 在m较小时，直接把它设置为点权求树上的直径 m较大时，可先拓展30次，得到最长的那条链，根据链的结点数和（度-1）的和，套公式计算
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 100;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
vector<int> to[N];
int d[N];
int aa[N];
int siz[N];
int sum[N];
int f[N];
int c = 1;
void dfs1(int u, int fa) {
for (auto v: to[u]) {
if (v == fa)continue;
f[v] = f[u] + aa[v];
siz[v]=siz[u]+1;
sum[v]=sum[u]+d[v]-1;
if (f[v] > f[c])c = v;
dfs1(v, u);
}
}
int ksm(int a, int b) {
int ans = 1;
while (b) {
if (b & 1)ans = ans * a%mod;
a = a * a%mod;
b >>= 1;
}
return ans;
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
to[u].push_back(v);
to[v].push_back(u);
d[u]++;
d[v]++;
}
if (m <= 30) {
for (int i = 1; i <= n; i++) {
aa[i] = (d[i] - 1) * (ksm(2, m) - 1) + 1;
}
c=1;
f[1] = aa[1];
dfs1(1, -1);
f[c] = aa[c];
dfs1(c, -1);
cout << f[c] << '\n';
}else{
for (int i = 1; i <= n; i++) {
aa[i] = (d[i] - 1) * (ksm(2, 30) - 1) + 1;
}
c=1;
f[1]=aa[1];
dfs1(1,-1);
f[c]=aa[c];
siz[c]=1;
sum[c]=d[c]-1;
dfs1(c,-1);
int res=(ksm(2, m) - 1+mod)%mod*sum[c]%mod+siz[c];
res%=mod;
cout<<res<<'\n';
}
for(int i=1;i<=n;i++){
d[i]=0;
to[i].clear();
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
1010女神的睿智
模拟题意
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int a[10][10];
int n[10];
void solve(){
n[1]=0,n[2]=0,n[3]=0;
cin>>s;
for(int i=0;i<8;i++){
if(s[i]=='R') n[1]++,a[0][i]=1;
if(s[i]=='G') n[2]++,a[0][i]=2;
if(s[i]=='B') n[3]++,a[0][i]=3;
}
for(int i=0;i<8;i+=2)a[1][i]=a[0][i];
for(int i=0;i<8;i+=4)a[2][i]=a[1][i];
if(a[2][0]==a[2][4]){
if(a[2][0]==1) cout<<'R'<<'\n';
if(a[2][0]==2) cout<<'G'<<'\n';
if(a[2][0]==3) cout<<'B'<<'\n';
}
else{
if(n[a[2][0]]==n[a[2][4]]){
cout<<'N'<<'\n';
return ;
}
if(n[a[2][0]]<n[a[2][4]]) a[2][0]=a[2][4];
if(a[2][0]==1) cout<<'R'<<'\n';
if(a[2][0]==2) cout<<'G'<<'\n';
if(a[2][0]==3) cout<<'B'<<'\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _ = 1;
cin >> _;
while (_--) solve();
return 0;
}1011在 A 里面找有 C 的 B
C是固定的，去找再B2中是否存在的话，哈希处理完是O（n）的； 然后把符合条件的B1用AC自动机，找是否在A中出现过
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn=1e6+10;
const int N = 1e6+10;
char str[maxn*10],buf[maxn];
int ans[maxn],n;
int ct[maxn];
int F[maxn];
struct AC {
int tot,pre[maxn][26],fail[maxn],pass[maxn];//pass用来表示这个点是单词的结尾，fail是失配指针，pre是儿子
int L,R,que[maxn];//队列部分的操作
vector<int>G[maxn];//x的失配指针到x是一条边，这样存一个图，从0结点就能一直跳了
int newnode() {
tot++;
for(int i=0; i<26; i++)pre[tot][i]=0;
fail[tot]=pass[tot]=ans[tot]=0;
return tot;
}//在给点赋值的同时进行初始化
void init() {
L=R=0;
tot=-1;
for(int i=1;i<=5e5+10;i++)ct[i] = F[i] =0 ;
newnode();
}
void insert(int q) {
int len=strlen(buf);
int cur=0;
for(int i=0; i<len; i++) {
int t=buf[i]-'a';
if(!pre[cur][t])pre[cur][t]=newnode();
cur=pre[cur][t];
}
pass[cur]=1;
ct[q]=cur;
}
void build() {
for(int i=0; i<26; i++) {
if(pre[0][i])que[R++]=pre[0][i];
}
while(L<R) {
int cur=que[L++];
G[fail[cur]].push_back(cur);
for(int i=0; i<26; i++) {
if(!pre[cur][i])pre[cur][i]=pre[fail[cur]][i];//建立fail指针
else {
que[R++]=pre[cur][i];
fail[pre[cur][i]]=pre[fail[cur]][i];
}
}
}
}
void dfs(int x) {
for(int i=0; i<G[x].size(); i++) {
int y=G[x][i];
dfs(y);
ans[x]+=ans[y];
}
}
void find() {
int len=strlen(str);
int cur=0;
for(int i=0; i<len; i++) {
int t=str[i]-'a';
cur=pre[cur][t];
ans[cur]++;
}
dfs(0);
}
void roll(){
for(int i=1;i<=6e5+100;i++)G[i].clear();
}
} AC;
char s2[maxn],t2[maxn];
ll a[maxn];
ll hl[maxn],hr[maxn];
ll bas = 13313;
void init(){
a[0]=1;
for(int i=1; i<=100100; i++) a[i]=a[i-1]*bas;
}
ll qu(ll c[],int l,int r)
{
return c[r]-c[l-1]*a[r-l+1];
}
void solve() {
scanf("%d",&n);
scanf("%s %s",str,s2);
int l2=strlen(s2);
for(int i=1; i<=l2; i++) {
hr[i]=hr[i-1]*bas+s2[i-1];
}
AC.init();
for(int j=1; j<=n; j++) {
scanf("%s %s",buf,t2);
int l=strlen(t2);
// cout<<j<<endl;
for(int i=1; i<=l; i++) {
hl[i]=hl[i-1]*bas+t2[i-1];
}
for(int i=1;i<=l-l2+1;i++){
if(qu(hr,1,l2)==qu(hl,i,i+l2-1)){
AC.insert(j);
F[j] = 1;
break;
}
}
}
AC.build();
AC.find();
bool f = 0;
for(int i=1; i<=n; i++) {
if(ans[ct[i]] && F[i] !=0 &&!f)printf("%d",i),f=1;
else if(ans[ct[i]] && F[i] !=0)printf(" %d",i);
}
printf("\n");
AC.roll();
}
signed main(){
init();
int T=1;
scanf("%d",&T);
while(T--)solve();
return 0;
}
