重塑一区荣光0425
序言
反复抓，抓反复，以昨天中午第一届一区✓编程大会为契机，深刻学习会议精神，加强提升编程能力体系化建设，把强化编程能力作为一区✓重点性，经常性工作
继续编程大业
11.二分图染色
代码
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <regex>
using namespace std;
#define ll long long
const int maxn = 1e7 + 10;
const int mod = 1e9 + 7;
ll mul[maxn];
ll inv[maxn];
ll f[maxn];
void init() {
mul[0] = 1;
for (int i = 1; i < maxn; i++) {
mul[i] = (mul[i - 1] * i) % mod;
}
inv[0] = inv[1] = 1;
for (int i = 2; i < maxn; i++) {
inv[i] = (ll) (mod - mod / i) * inv[mod % i] % mod;
}
for (int i = 1; i < maxn; i++) {
inv[i] = (inv[i - 1] * inv[i]) % mod;
}
f[0] = 1;
f[1] = 2;
for (int i = 2; i < maxn; i++) {
f[i] = 2ll * i * f[i - 1] % mod - 1ll * (i - 1) * (i - 1) % mod * f[i - 2] % mod;
f[i] = (f[i] % mod + mod) % mod;
}
}
ll C(int n, int m) {
return mul[n] * inv[m] % mod * inv[n - m] % mod;
}
ll A(int n, int m) {
return mul[n] * inv[n - m] % mod;
}
void solve(int n) {
ll ans = 0;
for (int i = 0; i <= n; i++) {
ans += ((i & 1) ? -1LL : 1LL) * C(n, i) * A(n, i) % mod * f[n - i] % mod * f[n - i] % mod;
ans = (ans % mod + mod) % mod;
}
cout << ans << endl;
}
int main() {
init();
int n;
cin >> n;
solve(n);
return 0;
}
12.合并回文子串
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 55;
int dp[N][N][N][N];
int main()
{
int T;
cin>>T;
while(T--)
{
string s1,s2;
cin>>s1>>s2;
int len1 = s1.size();
int len2 = s2.size();
int ans = 0;
for(int x = 0;x <= len1; x++) //枚举长度
for(int y = 0;y <= len2; y++) //枚举长度
for(int i=1,j=x;j<=len1;i++,j++) //枚举区间
for(int k=1,l=y;l<=len2;k++,l++){ //枚举区间
if(x+y<=1) dp[i][j][k][l] = 1; //单独一个字母是回文
else{
dp[i][j][k][l] = 0; //多组读入 初始化
if(x>1 && s1[i-1]==s1[j-1] && dp[i+1][j-1][k][l])
dp[i][j][k][l] = 1;
if(y>1 && s2[k-1]==s2[l-1] && dp[i][j][k+1][l-1])
dp[i][j][k][l] = 1;
if(x &&y && s1[i-1]==s2[l-1] && dp[i+1][j][k][l-1])
dp[i][j][k][l] = 1;
if(x &&y && s2[k-1]==s1[j-1] && dp[i][j-1][k+1][l]) //四种状态转移
dp[i][j][k][l] = 1;
}
if(dp[i][j][k][l]) ans= max(ans,x+y);
// 意味着区间i~j 和k~l 能构成回文，则长度为(j-i+1 + k-l+1) 即 (x+y)
}
cout<<ans<<endl;
}
return 0;
}
13.黑白树
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+7;
int h[N],e[N*2],ne[N*2],idx;
int k[N],ans;
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
int DFS(int u,int fa)
{
int num = 0;
for(int i=h[u];i!=-1;i=ne[i]){
int j = e[i];
if(j==fa) continue;
num = max(num,DFS(j,u)); //所有已经染过色的孩子能覆盖到的最大值
}
if(num==0){ //所有染过色的孩子都覆盖不到它
ans++;return k[u]-1;
}
k[fa] = max(k[fa],k[u]-1); //维护每个结点能往上覆盖的最大距离
return num-1;
}
int main()
{
int n,t;
cin>>n;
memset(h,-1,sizeof h);
for(int i=2;i<=n;i++){
cin>>t;
add(t,i),add(i,t);
}
for(int i=1;i<=n;i++) cin>>k[i];
DFS(1,0);
cout<<ans<<endl;
return 0;
}
14.城市网络
代码
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 2e5 + 10 ;
typedef long long ll ;
vector<int> v[maxn] ;
int a[maxn] , f[maxn][20] , dep[maxn] , to[maxn] ;
void dfs(int p , int fa){
int x = fa ;
for(int k = 19 ; k >= 0 ; k--)
if(f[x][k] && a[f[x][k]] <= a[p]) x = f[x][k] ; //如果x往上跳2^k步这个点存在，且这个点的权值比a[p]要小，就跳到这个点再往上跳
if(a[x] > a[p]) f[p][0] = x ; //判断比a[p]大的点到底是x还是x的上面那个点
else f[p][0] = f[x][0] ;
//向上倍增的找到第一个比p权值大的点
for(int i = 1 ; i < 20 ; i++) f[p][i] = f[f[p][i-1]][i-1] ;
dep[p] = dep[fa] + 1 ; //维护高度
int num = v[p].size() ;
for(int i = 0 ; i < num ; i++){
int to = v[p][i] ;
if(to == fa) continue ;
dfs(to , p) ; //搜子树
}
}
int n , q ;
int main(){
ios::sync_with_stdio(false) ;
cin.tie(0) ;
cout.tie(0) ;
cin >> n >> q ;
for(int i = 1 ; i <= n ; i++) cin >> a[i] ;
for(int i = 1 ; i < n ; i++){
int x , y ;
cin >> x >> y ;
v[x].push_back(y) ;
v[y].push_back(x) ;
}
for(int i = n + 1 ; i <= n + q ; i++){
int x , y , c ;
cin >> x >> y >> c ;
v[i].push_back(x) ;
v[x].push_back(i) ;
a[i] = c ;
to[i-n] = y ; //记录对应的终点
}
dfs(1 , 0) ;
for(int i = 1 ; i <= q ; i++){
int ans = 0 ;
int x = i + n ; //i+n是第i个询问的起点
for(int k = 19 ; k >= 0 ; k--){ //k从大到小枚举
if(dep[f[x][k]] >= dep[to[i]]){ //如果跳完之后深度小于目标点深度就已经走过了，跳跃高度要减小
ans += (1 << k) ; //点数加2^k
x = f[x][k] ; //向上跳2^k个点
}
}
cout << ans << endl ;
}
return 0 ;
}
15.树
代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 307;
const int mod = 1e9+7;
LL fac[N]; //阶乘
LL inv[N]; //阶乘的逆元
void init()
{
fac[0] = 1; inv[0] = 1;
fac[1] = 1; inv[1] = 1;
for(int i=2;i<N;i++)
inv[i] = (mod-mod/i)*inv[mod%i]%mod , fac[i] = i;
for(int i=2;i<N;i++)
inv[i] = inv[i]*inv[i-1]%mod , fac[i] = fac[i]*fac[i-1]%mod;
}
LL C(int a,int b){
return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
LL A(int a,int b){
return fac[a]*inv[a-b]%mod;
}
int main()
{
init();
int n,k,t;
cin>>n>>k;
for(int i=1;i<=(n-1)*2;i++) cin>>t;
LL ans = 0;
for(int i=1;i<=k&&i<=n;i++)
ans = (ans + C(n-1,i-1)*A(k,i)%mod)%mod;
cout<<ans<<endl;
return 0;
}
16.Shortest Path
代码
#include<stdio.h>
#include<string.h>
using namespace std;
#define ll long long int
struct node
{
int from;
int to;
int w;
int next;
}e[350000];
int cont;
int head[150000];
int size[150000];
ll output;
void add(int from,int to,int w)
{
e[cont].to=to;
e[cont].w=w;
e[cont].next=head[from];
head[from]=cont++;
}
void Dfs(int u,int from,int prew)
{
size[u]=1;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
int w=e[i].w;
if(v==from)continue;
Dfs(v,u,w);
size[u]+=size[v];
}
if(size[u]%2==1)output+=prew;
}
int main()
{
int n;
int t;scanf("%d",&t);
while(t--)
{
output=0,cont=0;
scanf("%d",&n);
memset(head,-1,sizeof(head));
for(int i=1;i<=n-1;i++)
{
int x,y,w;scanf("%d%d%d",&x,&y,&w);
add(x,y,w);add(y,x,w);
}
Dfs(1,-1,0);
printf("%lld\n",output);
}
}
17.Contest
代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn=2e5+10;
const LL mod=1e9+7;
const double pi=acos(-1.0);
inline LL read()
{
LL X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
LL n;
LL c[maxn];
LL a[maxn][3];
pair<LL,LL> p[maxn];
void add(LL x,LL d)
{
while(x<=n){
c[x]+=d;
x+=(x&(-x));
}
}
LL query(LL x)
{
LL ans=0;
while(x>0){
ans+=c[x];
x-=(x&(-x));
}
return ans;
}
int main()
{
scanf("%lld",&n);
for(LL i=1;i<=n;i++){
scanf("%lld%lld%lld",&a[i][0],&a[i][1],&a[i][2]);
}
LL res=0;
for(LL i=0;i<3;i++){
for(LL j=i+1;j<3;j++){
for(LL k=1;k<=n;k++){
p[k].first=a[k][i];p[k].second=a[k][j];
}
sort(p+1,p+1+n);
memset(c,0,sizeof(c));
/*for(LL k=1;k<=n;k++){
printf("%lld %lld\n",p[k].first,p[k].second);
}
printf("----\n");*/
for(LL k=1;k<=n;k++){
res+=(query(n)-query(p[k].second));
add(p[k].second,1);
}
}
}
printf("%lld\n",res/2);
return 0;
}
18.Xorto
代码
#include<bits/stdc++.h>
using namespace std;
int a[1010];
int sum[1010];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],sum[i] = sum[i-1]^a[i];
long long ans=0;
map<int ,int> mp;
for(int i=2;i<=n;i++){
for(int k=1;k<i;k++) mp[sum[i-1]^sum[k-1]]++;
for(int j=i;j<=n;j++) ans += mp[sum[j]^sum[i-1]];
}
cout<<ans<<endl;
return 0;
}
19.Treepath
代码
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int head[maxn],cnt,n,u,v,depth[2];
ll ans;
struct node{
int to,next;
}e[maxn<<1];
void add(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int son,int fa,int len){
depth[len%2]++;
for(int i=head[son];i;i=e[i].next){
if(e[i].to!=fa){
dfs(e[i].to,son,len+1);
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
scanf("%d %d",&u,&v);
add(u,v),add(v,u);
}
dfs(1,1,1);
ans=1ll*depth[0]*(depth[0]-1)+1ll*depth[1]*(depth[1]-1);
printf("%lld\n",ans/2);
return 0;
}
20.K-th Number
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
int a[MAX],b[MAX];
int qq[MAX],sum[MAX];
int n,k;
ll M;
int ok(int x) {
ll sum = 0;
for(int i = 1; i<=n; i++) qq[i] = a[i] >= x;
int l = 1,r = 1,tmp = 0;
while(l<=r && r<=n) {
tmp += qq[r];
while(tmp >= k && l<=r) {
tmp -= qq[l];
l++;
}
sum += l-1;
r++;
}
// sum--;
return sum>=M;
}
int main() {
int t;
cin>>t;
while(t--) {
scanf("%d%d%lld",&n,&k,&M);
for(int i = 1; i<=n; i++) scanf("%d",a+i),b[i] = a[i];
// int l = 0,r = *max_elememt(a+1,a+n+1); 这样不行 太大了。
sort(b+1,b+n+1);
int l=1,r=n,m,ans;
while(l<=r) {
int mid=(l+r)>>1;
if(ok(b[mid]))
l = mid+1,ans=mid;//
else r = mid-1;
}
printf("%d\n",b[ans]);
}
return 0 ;
}
今天就这10道了哥们儿们 理性操作 给二三区点面子
有条件的同学可以点开链接看看学学，讲得挺详细的
补几个学习链接 代码相关的 减少点浪费题的负罪感
1.数据结构学习：http://t.csdnimg.cn/mmhvZ 适合入门宝宝学习，主要是学习数据结构思维吧
2.同样是数据结构，多一点内容的链接：http://t.csdnimg.cn/PWF2K