2023年新疆ICPC VP

3h6题619罚时，solo铜，大概rk13 alt B

看了下赛时提交，大部分都是数1的个数判断硬算

其实dfs搜大于2的连通块个数就行，1个是E，5个是Y，其他S

using namespace std;
string a[1000100];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int cnt=0,ans=0;
void dfs(int x,int y,int s)
{
    if(s==2) ans++;
    a[x][y]='0';
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0&&yy>=0&&a[xx][yy]=='1')
        {
            dfs(xx,yy,s+1);
        }
    }
}
int main()
{
    while(cin>>a[cnt])
    {
        cnt++;
    }
    for(int i=0;i<cnt;i++)
    {    
        int n=a[i].size();
        for(int j=0;j<n;j++)
        {    
            if(a[i][j]=='1')
            dfs(i,j,1);
        }
    }
    if(ans==1)
        cout<<"E"<<endl;
    else if(ans==5)
        cout<<"Y"<<endl;
    else
        cout<<"S"<<endl;
}

简单的模拟，两个map一个存上联出现过的，一个存上联每个数对应的

using namespace std;
#define int long long
int n,a[100100],cnt=1;
map<int,int>s1,s2;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s1[a[i]]=1;
    }
    for(int i=0;i<n;i++)
    {
        if(s2[a[i]])
            cout<<s2[a[i]]<<' ';
        else
        {
            for(int i=cnt;;i++)
            {
                if(s1[i]==0)
                {
                    cnt=i;
                    break;
                }
            }
            cout<<cnt<<' ';
            s2[a[i]]=cnt;
            cnt++;
        }
    }
    
}

回文只要(i,j)(n-i+1,j)(i,m-j+1)(n-i+1,m-j+1)相等即可一开始思路错，想把四个位置变相同，wa1发之后发现要讨论重叠情况，直接算四个点不改状态，ans/4即可

using namespace std;
#define int long long
int n,m,ans=0;
char s[1010][1010];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>s[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char a=s[i][j];
            char b=s[n-i+1][j];
            char c=s[i][m-j+1];
            char d=s[n-i+1][m-j+1];
            int mi=1145141918;
                for(char k='a';k<='z';k++)
                {
                    int res=0;
                    res+=min(abs(k-a),26-abs(k-a));
                    res+=min(abs(k-b),26-abs(k-b));
                    res+=min(abs(k-c),26-abs(k-c));
                    res+=min(abs(k-d),26-abs(k-d));
                    mi=min(res,mi);
                }
                ans+=mi;
        }
    cout<<ans/4<<endl;
}

签到

using namespace std;
#define int long long
int n,a,b;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>a>>b;
    int xx=((n-a+2)+n)*(a-1)/2+b;
    //cout<<n-a+2<<' '<<xx<<' '<<endl;
    cout<<char(xx%26+'A'-1)<<endl;
}

一开始觉得是最小生成树，抄个板子交一发wa，把英文题面拿去翻译一下才读懂，贪心即可

using namespace std;
#define int long long
int sum,res,n,d[200100];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>d[i];
    }
    for(int i=1;i<=n;i++)
    {
    int x=min(d[i]-1,(n-1)*2-n-sum);
    res+=(x+1)*i*i;
    sum+=x;
    }
    if(sum<(n-1)*2-n) 
        cout<<-1<<endl;
    else 
        cout<<res<<endl;
}

逆天签到，我第一下直接被骗建树，吃两发wa，然后回忆了一下洛谷一道类似的，直接统计入度，C（n,2）即可，（然后没开ll又wa一发。。）

using namespace std;
#define int long long
vector<int>a[100100];
int n,d[100100],ans;
signed main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int ui,vi;
        cin>>ui>>vi;
        d[ui]++,d[vi]++;
    }
    for(int i=0;i<n;i++)
        ans+=d[i]*(d[i]-1)/2;
    cout<<ans<<endl;
}

因为VP时候有正榜，不会乱开题，一坤h差不多切完6 题了，比去年ccpc5h开一题进步太多了，win