A枚举 235
#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second
using namespace std;
int va[200] = {0,5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,
7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,0,1,
0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3};
int vb[50] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
signed main()
{
set<string> v;
int n = 100;
for(int y1=1;y1<=n;y1++)
{
if(va[y1]!=2) continue;
for(int y2=y1+1;y2<=n;y2++)
{
if(va[y2]!=0) continue;
for(int y3=y2+1;y3<=n;y3++)
{
if(va[y3]!=2) continue;
for(int y4=y3+1;y4<=n;y4++)
{
if(va[y4]!=3) continue;
for(int m1=y4+1;m1<=n;m1++)
{
for(int m2=m1+1;m2<=n;m2++)
{
for(int m3=m2+1;m3<=n;m3++)
{
for(int m4=m3+1;m4<=n;m4++)
{
int x1 = va[m1],x2 = va[m2],d1 = va[m3],d2 = va[m4];
int mm = x1*10+x2,dd = d1*10+d2;
if(mm<=12&&mm>=1&&dd>=1&&dd<=vb[mm])
{
char a = x1+'0',b = x2+'0',c = d1+'0',d = d2+'0';
string s;
s += a;s += b;s += c;s += d;
v.insert(s);
}
}
}
}
}
}
}
}
}
cout<<v.size();
for(auto t:v) cout<<t<<"\n";
}
B枚举0的个数,公式求一下。 11027421
C思维
#include<bits/stdc++.h>
#define int long long
#define db double
using namespace std;
const int N = 2e5+10;
int n;
int va[N],vb[N];
signed main()
{
scanf("%lld",&n);
int anwl = 0,anwr = 2e9;
for(int i=1;i<=n;i++)
{
scanf("%lld %lld",&va[i],&vb[i]);
int l = va[i]/(vb[i]+1)+1;
int r = va[i]/vb[i];
anwl = max(anwl,l);
anwr = min(anwr,r);
}
printf("%lld %lld",anwl,anwr);
return 0;
}
D搜索+剪纸优化
#include<bits/stdc++.h>
#define int long long
#define db double
using namespace std;
const int N = 100;
struct Node{
int a,b,c;
}va[N];
int T,n;
int vis[N];
int sta[50000];
int suc = 0;
void dfs(int now,int tim,int sum,int res)
{
if(suc) return ;
if(sta[res]==-1) return ;
if(sum==n)
{
suc = 1;
return ;
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
if(va[i].b<tim)
{
sta[res] = -1;
return ;
}
vis[i] = 1;
dfs(i,tim+va[i].c,sum+1,res+(1ll<<i));
vis[i] = 0;
}
}
signed main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
suc = 0;
for(int i=1;i<=n;i++) vis[i] = 0;
for(int i=0;i<=(1ll<<n);i++) sta[i] = 0;
for(int i=1;i<=n;i++)
{
int a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
va[i] = {a,a+b,c};
}
for(int i=1;i<=n;i++)
{
vis[i] = 1;
dfs(i,0+va[i].c,1,(1ll<<i));
vis[i] = 0;
}
if(suc) printf("YES\n");
else printf("NO\n");
}
return 0;
}
E动态规划,定义dp[i][j]为用到第i个,结尾为j最少要删多少个
#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second
using namespace std;
const int N = 1e5+10;
int n,m;
int va[N];
int l[N],r[N];
int dp[N][10];
int get(int x)
{
while(x)
{
if(x<10) return x;
x /= 10;
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>va[i];
l[i] = get(va[i]),r[i] = va[i]%10;
}
for(int i=1;i<=n;i++) for(int j=0;j<=9;j++) dp[i][j] = 1e9;
for(int i=0;i<=9;i++)
{
if(i==r[1]) dp[1][i] = 0;
else dp[1][i] = 1;
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<=9;j++)
{
if(j==r[i]) dp[i][j] = min(dp[i][j],dp[i-1][l[i]]);
dp[i][j] = min(dp[i][j],dp[i-1][j]+1);
}
}
int minn = 1e9;
for(int i=0;i<=9;i++) minn = min(minn,dp[n][i]);
cout<<minn;
return 0;
}
F dfs+bfs
#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second
using namespace std;
int T,n,m;
char va[55][55];
int vis[55][55];
int dx[8] = {1,-1,0,0,-1,-1,1,1};
int dy[8] = {0,0,1,-1,-1,1,-1,1};
bool dfs(int A,int B)
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
vis[i][j] = 0;
}
queue<PII > q;
q.push({A,B});
vis[A][B] = 1;
while(q.size())
{
auto now = q.front();q.pop();
int x = now.fi,y = now.se;
for(int i=0;i<8;i++)
{
int xx = x+dx[i],yy = y+dy[i];
if(xx<1||xx>n||yy<1||yy>m) return true;
if(va[xx][yy]=='0'&&!vis[xx][yy])
{
vis[xx][yy] = 1;
q.push({xx,yy});
}
}
}
return false;
}
void bfs(int A,int B)
{
queue<PII > q;
q.push({A,B});
while(q.size())
{
auto now = q.front();q.pop();
int x = now.fi,y = now.se;
for(int i=0;i<4;i++)
{
int xx = x+dx[i],yy = y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&va[xx][yy]=='1')
{
va[xx][yy] = '0';
q.push({xx,yy});
}
}
}
}
signed main()
{
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>va[i][j];
}
int ans = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(va[i][j]=='1')
{
if(!dfs(i,j))
va[i][j] = '0';
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(va[i][j]=='1')
{
ans++;
bfs(i,j);
}
}
}
cout<<ans;
if(T!=0) cout<<"\n";
}
return 0;
}
G 维护一个后缀即可
#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second
using namespace std;
const int N = 5e5+50;
int n,m;
char c1,c2;
char s[N];
int sumr[N];
signed main()
{
cin>>m>>s+1>>c1>>c2;
n = strlen(s+1);
for(int i=n;i>=1;i--)
{
sumr[i] = sumr[i+1]+(s[i]==c2);
}
int ans = 0;
for(int i=1;i<=n;i++)
{
if(s[i]==c1&&i+m-1<=n)
ans += sumr[i+m-1];
}
cout<<ans;
return 0;
}
H 记录左右位置是谁
#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second
using namespace std;
const int N = 5e5+10;
int n,m;
int va[N];
int vis[N];
int l[N],r[N];
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>va[i];
for(int i=1;i<=n;i++)
{
if(i==1) l[i] = -1,r[i] = i+1;
else if(i==n) l[i] = i-1,r[i] = -1;
else l[i] = i-1,r[i] = i+1;
}
while(m--)
{
int minn = 1e18,idx = 0;
int now = 1;
while(now!=-1)
{
if(vis[now]==1) now = r[now];
else
{
if(minn>va[now])
{
minn = va[now];
idx = now;
}
now = r[now];
}
}
if(l[idx]!=-1) va[l[idx]] += va[idx];
if(r[idx]!=-1) va[r[idx]] += va[idx];
vis[idx] = 1;
r[l[idx]] = r[idx];
l[r[idx]] = l[idx];
}
int now = 1;
while(now!=-1)
{
if(vis[now]==1) now = r[now];
else
{
cout<<va[now]<<" ";
now = r[now];
}
}
return 0;
}
I LCA
#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 1e5+10;
int n,m;
int va[N];
int acc[N][25],cnt=22;
int dep[N],sum[N];
vector<PII > e[N];
void dfs(int now,int p)
{
acc[now][0] = p;
dep[now] = dep[p]+1;
for(auto t:e[now])
{
int spot = t.fi,w = t.se;
if(spot==p) continue;
sum[spot] = sum[now]+w;
dfs(spot,now);
}
}
int lca(int a,int b)
{
if(dep[a]<dep[b]) swap(a,b);
for(int i=cnt;i>=0;i--)
{
if(dep[acc[a][i]]>=dep[b])
a = acc[a][i];
}
if(a==b) return a;
for(int i=cnt;i>=0;i--)
{
if(acc[a][i]!=acc[b][i])
{
a = acc[a][i];
b = acc[b][i];
}
}
return acc[a][0];
}
int get(int a,int b)
{
int res = sum[a]+sum[b]-2*sum[lca(a,b)];
return res;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<n;i++)
{
int a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
e[a].pb({b,c});
e[b].pb({a,c});
}
dfs(1,0);
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=n;j++)
acc[j][i] = acc[acc[j][i-1]][i-1];
}
for(int i=1;i<=m;i++) scanf("%lld",&va[i]);
int ans = 0;
for(int i=1;i<m;i++) ans += get(va[i],va[i+1]);
for(int i=1;i<=m;i++)
{
int res = 0;
if(i==1) res = ans-get(va[i],va[i+1]);
else if(i==m) res = ans-get(va[i],va[i-1]);
else
{
res = ans-get(va[i],va[i-1])-get(va[i],va[i+1]);
res += get(va[i-1],va[i+1]);
}
printf("%lld",res);
if(i!=m) printf(" ");
}
return 0;
}
J 数据小的时候暴力枚举选择哪一天边可以,数据大直接-1
#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second
using namespace std;
const int N = 2e5+10;
int n,m;
PII va[N];
PII vb[N];
int acc[N];
int find(int x)
{
if(x!=acc[x]) acc[x] = find(acc[x]);
return acc[x];
}
bool check(int x)
{
for(int i=1;i<=n;i++) acc[i] = i;
for(int i=1;i<n;i++)
{
if(i==x) continue;
int a = va[i].fi,b = va[i].se;
int t1 = find(a),t2 = find(b);
acc[t1] = t2;
}
for(int i=1;i<=m;i++)
{
int a = vb[i].fi,b = vb[i].se;
int t1 = find(a),t2 = find(b);
if(t1==t2) return false;
}
return true;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<n;i++) cin>>va[i].fi>>va[i].se;
for(int i=1;i<=m;i++) cin>>vb[i].fi>>vb[i].se;
if(n*m>3e7||n*n>3e7)
{
cout<<-1;
return 0;
}
for(int i=n-1;i>=1;i--)
{
if(check(i))
{
cout<<i;
return 0;
}
}
cout<<-1;
return 0;
}
tql
害,都退役半年了。我感觉这次挺简单的,要是国赛就好了,上次国赛没打好,大三狗了还没拿到国一。
稳省一了。
orz