AC小菜

1520

996
l_y_f
-摆烂王-
slight

IINE

NFYD

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5;

int prime[N];
void getprime(int n)
{
for (int i = 2; i <= n/i; i++)
{
if (n % i == 0)
{
int s = 0;
while (n % i == 0)
{
s++;
n /= i;
}
prime[i] += s;
}
}
if (n > 1)
prime[n] += 1;
}
int main()
{
int n;
cin >> n;

for (int i = 2; i <= n; i++)
{
getprime(i);
}

for(int i=2;i<=n;i++)
{
if(prime[i]!=0)
printf("%d %d\n",i,prime[i]);
}
return 0;

}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,prime[1000005],cnt,st[1000005];

void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(st[i]==0)
{
prime[cnt++]=i;

}
for(int j=0;prime[j]<=n/i;j++)
{
st[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}

}

int main()
{
cin>>n;
get_prime(n);
for(int i=0;i<cnt;i++)
{
int ans=0,t=n;
while(t)
{
ans+=t/prime[i];
t/=prime[i];
}
if(ans)
cout<<prime[i]<<" "<<ans<<endl;
}
return 0;
}


dp+记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int T, n, mp[1005][1005], f[1005][1005];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

int dp(int a, int b)
{
int &t = f[a][b];
if (t != -1) return t;

t = 1;
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n && mp[a][b]+1 == mp[x][y])
t = max(t, dp(x, y) + 1);
}

return t;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
for (int i = 1; i <= T; i++)
{
cin >> n;
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
cin >> mp[j][k];

memset(f, -1, sizeof f);
int id, dis = 0;

for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
{
int t = dp(j, k);
if (t > dis || (t == dis && id > mp[j][k]))
{
id = mp[j][k];
dis = t;
}
}

printf("Case #%d: %d %d\n", i, id, dis);
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int n,w[105];
vector<int> level[105];

int getmin(int l,int r)
{
int root=l;
for(int i=l;i<=r;i++)
{
if(w[root]>w[i])
root=i;
}

return root;
}
void dfs(int l,int r,int d)
{
if(l>r)
return ;

int t=getmin(l,r);
level[d].push_back(w[t]);

dfs(l,t-1,d+1);
dfs(t+1,r,d+1);
}

int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];

dfs(1,n,0);
for (int i = 0; level[i].size(); i ++ )
{
for(auto x:level[i])
cout<<x<<" ";
}

return 0;
}



#include<bits/stdc++.h>
using namespace std;
int n, w[105], L[105], R[105];
vector<int> level[105];

int getmin(int l, int r)
{
int root = l;
for (int i = l; i <= r; i++)
{
if (w[root] > w[i])
root = i;
}

return root;
}

int dfs(int l, int r)
{
if (l > r)
return 0;

int t = getmin(l, r);
L[t] = dfs(l, t - 1);
R[t] = dfs(t + 1, r);

return t;
}

void bfs(int t)
{
queue<int> q;
q.push(t);
while (q.size())
{
int x = q.front();
q.pop();
cout << w[x] << " ";
if (L[x] != 0)
q.push(L[x]);
if (R[x] != 0)
q.push(R[x]);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];

int rt = dfs(1, n);

bfs(rt);

return 0;
}


# SG函数+记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N=2005;
const int M=6005;
int n,m,k,e[M],h[N],ne[M],sg[N],idx;
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}

int SG(int x)
{
if(sg[x]!=-1) return sg[x];

unordered_set<int> S;
for(int i=h[x];i!=-1;i=ne[i])
{
S.insert(SG(e[i]));
}

for(int i=0;;i++)
{
if(S.count(i)==0)
return sg[x]=i;
}
}
int main()
{
memset(h, -1, sizeof h);
memset(sg,-1,sizeof sg);
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
}
int res=0;

for(int i=0;i<k;i++)
{
int x;
cin>>x;
res^=SG(x);
}

if(res)
cout<<"win";
else
cout<<"lose";
return 0;
}



md ! l的最大值是N！！！！ pat真是服了

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, k, g[1005][1005];

int main()
{
cin >> n >> m;
int x, y;
while (m--) {
cin >> x >> y;
g[x][y] = 1;
g[y][x] = 1;
}
cin >> k;
int l, a[205] = { 0 }, f;
for (int t = 1; t <= k; t++)
{
f = 1;
cin >> l;
for (int i = 0; i < l; i++) cin >> a[i];

for (int i = 0; i < l-1; i++)
for (int j = i+1; j < l; j++)
if (g[a[i]][a[j]] == 0)
f = 0;

int mor = 205;
if (f)
{
int flag = 0;
for (int i = 1; i <= n; i++)
{
int fl = 1;
for (int j = 0; j < l; j++)
{
if (g[i][a[j]] == 0)
{
fl = 0;
break;
}
}

if (fl)
{
flag = 1;
mor=i;
break;
}
}
if (flag)
printf("Area %d may invite more people, such as %d.\n", t, mor);

else
printf("Area %d is OK.\n", t);
}

else
printf("Area %d needs help.\n", t);
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;

int n, k, e[100005], ne[100005], h;
int main()
{
cin >> h >> n >> k;

while (n--)
{
cin >> adr >> num >> next;
}
vector<int> c;
int t = 0;
for (int i = h; i != -1; i = ne[i])
c.push_back(i),t++;

for (int i = t - (t % k); i >= 0; i -= k)
{
for (int j = 0; j < k && i + j < t; j++)
{
if (j != k-1 && i + j != t - 1)
printf("%05d %d %05d\n", c[i + j], e[c[i + j]], c[i + j + 1]);
else
{
if (i + j == k-1||(i+j==t-1&&t<k))//!!!!!!!!!!!
printf("%05d %d -1", c[i + j], e[c[i + j]]);
else
printf("%05d %d %05d\n", c[i + j], e[c[i + j]], c[i- k]);
}

}
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
string alp[26][7],wd[1005];

int main()
{
for (int i = 0; i < 26; i ++ )
for (int j = 0; j < 7; j ++ )
cin>>alp[i][j];

string s;
getchar();
getline(cin,s);

vector<string> res;
string str;
for(int i=0;i<s.size();i++)
{
str="";
while(s[i]>='A'&&s[i]<='Z')
{
str+=s[i];
i++;
}
if(str!="")//!!!!!!!!
res.push_back(str);

}

for(int i=0;i<res.size();i++)
{
if(i)
cout<<endl;
for(int k=0;k<7;k++)
{
for(int j=0;j<res[i].size();j++)
{
if(j)
cout<<" ";
cout<<alp[res[i][j]-'A'][k];
}
cout<<endl;
}

}
return 0;
}



AC小菜
11天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
int a[105],m[105],n;

void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
x=1,y=0;
else
{
exgcd(b,a%b,y,x);
y-=a/b*x;
}

}
int main()
{
cin>>n;
ll M=1;
for(int i=0;i<n;i++)
{
cin>>m[i]>>a[i];
M*=m[i];
}
ll res=0;
for (int i = 0; i < n; i ++ )
{
ll t=M/m[i],x,y;
exgcd(t,m[i],x,y);
res+=a[i]*t*x;
}

cout<<(res%M+M)%M;
return 0;
}


AC小菜
13天前

dijkstra模板稍微变形

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, k, dist[1005], g[1005][1005], p[1005], st[1005];

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[p[0]] = 0;

for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (st[j] == 0 && (t == -1 || dist[t] > dist[j]||(dist[t]>=dist[j]&&p[i]==j)))//变形
t = j;

st[t] = 1;
//cout << t << " ";
if (t != p[i])
{
return 0;
}

for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);

}
//cout << endl;
return 1;
}
int main()
{
cin >> n >> m;
int a, b, c;
memset(g, 0x3f, sizeof g);
while (m--) {
cin >> a >> b >> c;
g[a][b] = c;
g[b][a] = c;

}
cin >> k;
while (k--)
{
memset(st, 0, sizeof st);
memset(p, 0, sizeof p);
for (int i = 0; i < n; i++)
cin >> p[i];

if (dijkstra())
cout << "Yes" << endl;
else

cout << "No" << endl;
}
return 0;
}


AC小菜
13天前

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
struct node
{
string s;
int l=-1,r=-1;
}tre[105];

string dfs(int t)
{
if (tre[t].l == -1 && tre[t].r == -1)
return "(" + tre[t].s + ")";
if (tre[t].l == -1 && tre[t].r != -1)
return "(" + tre[t].s + dfs(tre[t].r) + ")";

return "(" + dfs(tre[t].l) + dfs(tre[t].r) +tre[t].s +")";
}
int main()
{
cin >> n;
string s;
int l, r;
for (int i = 1; i <= n; i++)
{
cin >> s >> l >> r;
tre[i].s = s;
tre[i].l = l, tre[i].r = r;
}

int root = 0;
for (int i = 1; i <= n; i++)
{
int f = 1;
for (int j = 1; j <= n; j++)
{
if (i == tre[j].l || i == tre[j].r)
{
f = 0;
break;
}
}

if(f)
root = i;
}

cout<<dfs(root);

return 0;
}