2022高考集训1
这次真的考炸了······
T1 2A
分析
数组开小了aaaaaa......................(╯‵□′)╯︵┻━┻
一百分就这么没了。。。
主要就是判断是否合法
唯一合法的时候，就是按照规则重新组织 IP 后，输入的字符串 = 输出的字符串
有几个错误情况：
1.字符串中除了“.”和数字，有其他字符，貌似没有空格，不确定可以用cin.getline输入
2.前导零
3.第四个数字后面有“.”，第一个数字前有“.”
4.中间有好几个“.”连在一起
5.数字大于255（一定要开long long储存数字，防止爆int，一个数字最多26位，就算爆long long，也是负数）
AC 代码
#include
#include
using namespace std;
#define ll long long
char s[40];
bool vis;
ll ans[5];
int main(){
freopen("ip.in","r",stdin);
freopen("ip.out","w",stdout);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
cin.getline(s,40);
int l = strlen(s);
for(int i = 0;i < l;++i){//有无其他字符
if(!vis && s[i] != '.' && (s[i] < '0' || s[i] > '9')){
printf("NO\n");
vis = 1;
break;
}
}
//判断数字是否合法并记录数字
int t = 0;
while((s[t] < '0' || s[t] > '9') && t < l) t++;
if(!vis && t){
printf("NO\n");
vis = 1;
}
for(int i = 1;i <= 4;++i){
if(!vis && s[t] == '0'){
printf("NO\n");
vis = 1;
}
while(s[t] >= '0' && s[t] <= '9' && t < l){
ans[i] = ans[i]*10 + (s[t] ^ 48);
t++;
}
if(!vis && ans[i] > 255){
printf("NO\n");
vis = 1;
}
if(!vis && i == 4 && t != l){
printf("NO\n");
vis = 1;
}
while((s[t] < '0' || s[t] > '9') && t < l) t++;
}
if(!vis) printf("YES\n");
else{
for(int i = 1;i <= 4;++i){
if(ans[i] < 0 || ans[i] <= 255) printf("%lld",ans[i]);
else printf("255");
if(i != 4) printf(".");
}
}
return 0;
} T2 2B
分析
这道题也比较简单，没错，是“也比较简单”，T1纯属意外
因为PP和AP可以删除，AA不能删除
也就是说当目前字符串中，P的个数越多，越容易删除
所以优先删除AP更优
AC 代码
#include
#include
using namespace std;
#define ll long long
inline int in(){
int x = 0;
bool f = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 0;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
if(f) return x;
else return -x;
}
//先合并AP更优?
//emmm.....大概吧
char s[10010];
int f[10010];
int ans;
int main(){
freopen("apstr.in","r",stdin);
freopen("apstr.out","w",stdout);
scanf("%s",s);
int l = strlen(s);
f[0] = -1;
for(int i = 1;i <= l;++i) f[i] = i-1;
for(int i = 0;i < l;++i){
if(s[i] == 'A' && s[i+1] == 'P'){
f[i+2] = f[i];
i++;
continue;
}
if(f[i] >= 0 && s[i] == 'P'){
f[i+1] = f[f[i]];
continue;
}
if(s[i] == 'P' && s[i+1] == 'P'){
f[i+2] = f[i];
i++;
continue;
}
}
int t = l;
while(t >= 0){
ans++;
t = f[t];
}
printf("%d",ans-1);
return 0;
} T3 2C
分析
首先肯定是判断声明是否正确，再连接边
条件一:如果重复声明,则为错误声明
条件二:如果要连边的点未声明,则为错误声明
条件三:如果会连成菱形,则为错误声明
对于前两个条件，用map就能解决
对于第三个条件菱形
首先要明确什么是菱形：
对于A，B，C，D四个类
B和C有公共祖先A
而且B不是C的祖先，C也不是B的祖先
B和C都是D的祖先
由于直接处理的时间复杂度很高，Lyin大佬造的数据过不去，只是题库的数据太水了（啊不是）
所以我们将与B有公共祖先，且与B无祖孙关系的C点存一下
如果D同时连接B和C，直接break
用bitset直接做&运算会方便许多
AC 代码
#include
#include
#include T4 2D
分析
赛时eafoo大佬暴力过了，赛后经过lyin大佬的极强数据，卡掉了几种算法
Lyin大佬的O(n+2m+nα)算法
#include
#define fre(x) freopen( #x ".in", "r", stdin), freopen( #x ".out", "w", stdout )
using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb;
const int N = 1e6 + 10;
mt19937 mt( (ull)(new char) );
int Rand ( int l, int r ) { return uniform_int_distribution<>(l,r)(mt); }
int n, m, kn, km, kb, du[N]; vector vec[N];
struct BCJ
{
int fa[N], sm[N], sn[N], sd[N];
void Init ( int n ) { for( int i = 1; i <= n; ++i) fa[i] = i, sm[i] = 0, sn[i] = 1, sd[i] = du[i]; }
int Find ( int x ) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void Merge ( int x, int y )
{
int fx = Find(x), fy = Find(y); if( fx == fy ) return; if( sn[fx] > sn[fy] ) swap( fx, fy );
fa[fx] = fy, sm[fy] += sm[fx], sn[fy] += sn[fx], sd[fy] += sd[fx];
}
ll Calc ( int x ) { return sn[x] == 1 ? -LLONG_MAX : 0LL + 1LL * km * sm[x] + 1LL * kn * sn[x] + 1LL * kb * ( sd[x]-2LL*sm[x] ); }
}S;
struct Graph
{
struct Edge { int to, next; } E[N<<1];
int ind, head[N];
void Insert ( int u, int v ) { ++ind, ++du[u], E[ind].to = v, E[ind].next = head[u], head[u] = ind; }
void Link ( int u, int v ) { Insert( u, v ), Insert( v, u ); }
vector bin[N]; bool vis[N]; int top;
bool Select ( int k, int &u ) { while( bin[top].empty() && top <= k ) ++top; if( top > k ) return false; u = bin[top][ bin[top].size()-1 ], bin[top].pop_back(); return true; }
void Solve ()
{
for( int i = 1; i <= n; ++i) bin[ du[i] ].push_back( i ); top = 0;
for( int k = 1, u = 0; k <= n; ++k) while( Select( k, u ) )
{
if( vis[u] ) continue; vec[k].push_back(u), vis[u] = true, S.sm[u] = top;
for( int i = head[u]; i; i = E[i].next ) if( !vis[ E[i].to ] ) bin[ --du[ E[i].to ] ].push_back( E[i].to ), top = min( top, du[ E[i].to ] );
}
for( int i = 1; i <= n; ++i) vis[i] = 0;
ll maxi = -LLONG_MAX, maxk = 0;
for( int k = n; k >= 1; --k)
{
reverse( vec[k].begin(), vec[k].end() );
for( auto u : vec[k] ) { vis[u] = true; for( int i = head[u]; i; i = E[i].next ) if( vis[ E[i].to ] ) S.Merge( u, E[i].to ); }
for( auto u : vec[k] ) if( maxi < S.Calc( S.Find(u) ) ) maxi = S.Calc( S.Find(u) ), maxk = k;
}
cout << maxk << " " << maxi << "\n";
}
}G;
void Solve ()
{
cin >> n >> m >> km >> kn >> kb, kn = -kn;
for( int i = 1; i <= m; ++i) { int a, b; cin >> a >> b, G.Link( a, b ); }
S.Init(n), G.Solve();
}
signed main ()
{
fre(kdgraph);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); Solve(); return 0;
} 经过smtwy的不懈努力，终于调出了自己的代码，据说是与题解思路一样
赛时多打了个“=”，挂了50分
以下是smtwy大佬的思路
首先，先建图，建议用前向星（Lyin大佬的数据太强啦，vector太慢，会挂掉）（下面的建议原因相同，就不再一一解释了）
同时记录一下每个点的度
然后我们去枚举第k-degree图
将度为k的点存到一起
注意：会有孤立点，所以循环要从0开始，把孤立点删掉
然后从最大的k，倒序将原图恢复
因为k+1-degree是k-degree的子图
将度为k的点与度大于k的点合并
合并时要注意边界边的条数，因为度为k的点与其他连通图连接的位置是两个图的边界边
所以要-2
smtwy大佬的题解：
AC 代码
#include
#include
#include
using namespace std;
#define Re register int
#define ll long long
inline int in(){
int x = 0;
bool f = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 0;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
if(f) return x;
else return -x;
}
const int N = 1e6+10;
struct node{
int bl;//属于第几degree
int sn,sm,sb;//顶点数,边数,边界边数
}s[N];
int n,m;
int a,b,c;
int mx = -1,du;
int head[N],nxt[N << 1],to[N << 1],cnt;
int d[N];
int fa[N];
int q[N],l,r;
ll res,ans;
vector num[N];
inline void add(int u,int v){
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
inline int find(int x){
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
inline void merge(int u,int v){
int x = find(u);
int y = find(v);
if(x != y){//不属于同一k_degree
fa[y] = x;
s[x].sn += s[y].sn;
s[x].sm += s[y].sm + 1;
s[x].sb += s[y].sb - 2;//连接两个不同的k_degree,边界边会变成连通边,那么边界边会减少2
}else{
s[x].sb -= 2;
s[x].sm++;
}
}
int main(){
freopen("kdgraph.in","r",stdin);
freopen("kdgraph.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n = in();
m = in();
a = in();
b = in();
c = in();
ans = -1e17;
int x,y;
for(Re i = 1;i <= m;++i){
x = in();
y = in();
d[x]++;
d[y]++;
add(x,y);
add(y,x);
}
for(Re i = 1;i <= n;++i){//初始化
fa[i] = i;
s[i].sn = 1;
s[i].sb = d[i];
mx = max(mx,d[i]);
}
int tot = 0,mxx;
for(Re i = 0;i <= mx;++i){//枚举k-degree子图,将每个点分到不同子图中
l = 1;r = 0;
for(Re j = 1;j <= n;++j)
if(d[j] == i){
if(i == 0) tot++;
else q[++r] = j;
}
if(i == 0) continue;
while(l <= r){
int u = q[l];
l++;
tot++;
num[i].push_back(u);
s[u].bl = i;
for(int k = head[u];k;k = nxt[k]){
int v = to[k];
d[v]--;
if(d[v] == i) q[++r] = v;
}
}
if(tot == n){
mxx = i;
break;
}
}
//k+1_degree 属于 k_degree,所以倒序枚举,将图恢复
for(int i = mxx;i > 0;--i){
int sz = num[i].size();
for(int j = 0;j < sz;++j){
int u = num[i][j];
for(int k = head[u];k;k = nxt[k]){
int v = to[k];
if(i < s[v].bl) merge(u,v);
else if(i == s[v].bl && u < v) merge(u,v);
}
}
for(int j = 0;j < sz;++j){
int k = find(num[i][j]);
res = (ll)s[k].sm*a - (ll)s[k].sn*b + (ll)s[k].sb*c;
if(ans < res){//不用取等,因为i是倒序枚举的
du = i;
ans = res;
}
}
}
printf("%d %lld\n",du,ans);
return 0;
}