Educational Codeforces Round 1 个人总结A-E

A. Tricky Sum

数学，求\(1 \dots n\)的和减去小于等于n的二次幂乘2之和

LL f[40];

void solve()

{

	LL n;	cin>>n;

	LL ans=n+n*(n-1)/2;

	for(int i=0;i<=32;i++)

		if(f[i]<=n)

			ans-=(2ll*f[i]);

	cout<<ans<<endl;

    return;

}

void init()

{

	f[0]=1;

	for(int i=1;i<=32;i++)

		f[i]=f[i-1]*2;

}

int main()

{

    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);

    // 特殊输入 请注释上方，如__int128等

    int TC = 1;

    init();

    cin >> TC;

    for(int tc = 1; tc <= TC; tc++)

    {

        //cout << "Case #" << tc << ": ";

        solve();

    }

    return 0;

}

B. Queries on a String

模拟，给你一个字符串，操作\(n\)次,将\(l\),\(r\)区间的字符向右循环移动

观察到k很大时，移位发生循环，即有只有不循环的移位次数才是有效的，即每次字符串区间\(s[l, \dots,r]\)移位\((r-l+1)\%k\)次，时间复杂度为\(O(sn)\)
又观察到，令\(k=k\%(r-l+1)\),\(s[l,\dots,r]\)，

旋转得到\(s[r-k+1,\dots,r,l,\dots,r]\)

void solve()

{

	string 	op,t;	cin>>op;

	int m;	cin>>m;

	op="?"+op;

	while(m--)

	{

		int l,r,k;	cin>>l>>r>>k;

		int s=r-l+1;

		k%=s;

		if(k==0)	continue;

		vector<char> t;t.pb('?');

		for(int i=r-k+1;i<=r;i++)

			t.pb(op[i]);

		for(int i=l;i<r-k+1;i++)

			t.pb(op[i]);

		int j=1;

		for(int i=l;i<=r;i++)

			op[i]=t[j],j++;

	}

	for(int i=1;i<op.size();i++)

		cout<<op[i];

	cout<<endl;

    return;

}

D. Igor In the Museum

bfs，flood fill

给你一个图，问一个坐标所处的连通块有多少个\(.\)和\(*\)相邻

对每个连通块bfs一下，同时求\(.\)和\(*\)相邻的个数，然后记录一下连通块中的答案

const int N = 1010;

bool vis[N][N];

int n,m,k,cnt=0,ans[N][N];

vector<PII> pos;

char op[N][N];

int dx[]={-1,1,0,0},dy[]={0,0,-1,1};

void bfs(int t4,int t3)

{

    int s=0;

    vis[t4][t3]=true;

    pos.clear();    pos.pb({t4,t3});

    queue<PII> q;   q.push({t4,t3});

    while(!q.empty())

    {

        PII t=q.front();    q.pop();

        for(int i=0;i<4;i++)

        {

            int x=dx[i]+t.fi;

            int y=dy[i]+t.se;

            if(x<=0||x>n||y<=0||y>m)

                continue;

            if(op[x][y]=='*')

                s++;

            if(op[x][y]=='*'||vis[x][y])    continue;

            pos.pb({x,y});

            q.push({x,y});

            vis[x][y]=true;

        }

    }

    for(auto &it:pos)

        ans[it.fi][it.se]=s;

}

void solve()

{

    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            cin>>op[i][j];

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            if(op[i][j]=='.'&&!vis[i][j])

                bfs(i,j);

    while(k--)

    {

        int x,y;    cin>>x>>y;

        cout<<ans[x][y]<<endl;

    }

    return;

}

E. Chocolate Bar

记忆化搜索，DP

定义状态\(dp_{i,j,k}\)，分别代表矩形的长、宽、所需的面积,直接dfs即可

\(dp_{i,j,k}=min\{dp_{{i-x},j,k-z}+dp_{x,j,z}+j^2,
dp_{i,{j-y},k-z}+dp_{i,y,z}+i^2\}\) \((1 \leq x \leq \frac{i}{2},1 \leq y \leq \frac{j}{2},0 \leq z \leq k )\)

int f[35][35][55],n,m,k;

int dfs(int x,int y,int z)

{

    if(f[x][y][z]||x*y==z||z==0)

        return f[x][y][z];

    int res=1e9;

    for(int i=1;i<=x/2;i++)

        for(int j=0;j<=z;j++)

            res=min(res,dfs(i,y,j)+dfs(x-i,y,z-j)+y*y);

    for(int i=1;i<=y/2;i++)

        for(int j=0;j<=z;j++)

            res=min(res,dfs(x,i,j)+dfs(x,y-i,z-j)+x*x);

    f[x][y][z]=res;

    return res;

}

void solve()

{

    cin>>n>>m>>k;

    cout<<dfs(n,m,k)<<endl;

    return;

}

C. Nearest vectors

这题做的比较曲折，题意是求所有点中，点A和点B组成最小∠AOB的编号。

一开始没学过极角排序（没错，高中没讲这个晕），然后自己观察到了对四个象限，每个象限的点与原点O的斜率顺时针从大到小，思路是各个象限按斜率排序后插入集合，对不在象限的点特判处理。但莫名奇妙WA48，具体原因还在思考

后面学习了极角排序极角序，atan2又WA114（卡精度的），将读入从int换成long double就过了,我也和很多blog一样不知道为什么

const long double pi=acos(-1);

const double eps = 1e-11;

typedef pair<long double,int> PLDI;

void solve()

{

    vector<PLDI> a;

    int n;  cin>>n;

    for(int i=1;i<=n;i++)

    {

        long double x,y;    cin>>x>>y;

        a.pb({atan2(y,x),i});

    }

    sort(all(a));

    long double ans=1e6;

    int x,y;

    for(int i=0;i<n;i++)

    {

        long double t=a[(i+1)%n].fi-a[i].fi;

        if(t<eps)   t+=(2*pi);

        //cout<<t<<endl;

        if(t<ans)

            ans=t,x=a[(i+1)%n].se,y=a[i].se;

    }

    cout<<x<<" "<<y<<endl;

}

贴一下，自己vp赛时写的WA48

//  AC one more times

////////////////////////////////////////INCLUDE//////////////////////////////////////////

#include <bits/stdc++.h>

using namespace std;

/////////////////////////////////////////DEFINE//////////////////////////////////////////

#define fi first

#define se second

#define pb push_back

#define endl '\n'

#define all(x) (x).begin(), (x).end()

#define inf64 0x3f3f3f3f3f3f3f3f

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef pair<long long,long long> PLL;

////////////////////////////////////////CONST////////////////////////////////////////////

const int inf = 0x3f3f3f3f;

const int maxn = 2e6 + 6;

const double eps = 1e-11;

///////////////////////////////////////FUNCTION//////////////////////////////////////////

template<typename T>

void init(T q[], int n, T val){   for (int i = 0; i <= n; i++) q[i] = val;  }

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

bool cmp(int c, int d) { return c > d; }

//inline __int128 read(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

//inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}

LL get_quick_mod(LL a,LL b,LL p){   LL ans=1%p;while(b){    if(b&1) {ans=ans*a%p;}  a=a*a%p,b>>=1;    }    return ans;  }

const int mod = 1e8;

const int N = 1e5+10;

const double pi2=acos(-1);

#define double long double

struct Point

{

    long long  x,y;

    int id;

    double k=0;

        Point(long long x=0,long long y=0):x(x),y(y){}

};

int sign(double x)  // 符号函数

{

    if (fabs(x) < eps) return 0;

    if (x < 0) return -1;

    return 1;

}

typedef Point Vector;

Vector operator - (Vector A,Vector B)

{

    return Vector(A.x-B.x,A.y-B.y);

}

bool cmp1(struct Point c,struct Point d)

{

    return c.k>=d.k;

}

double dot(Point a, Point b)

{

    return a.x * b.x + a.y * b.y;

}

double get_length(Point a)

{

    return sqrt(dot(a, a));

}

double get_angle(Point a, Point b)

{

    return acos(dot(a, b) / get_length(a) / get_length(b));

}

vector<struct Point> a,a1,a2,a3,a4,a5;

int ans1=1,ans2=2;

void solve()

{

    int n;  cin>>n;

    for(int i=1;i<=n;i++)

    {

        struct Point t;

        cin>>t.x>>t.y;

        t.id=i;

        if(t.x==0||t.y==0)

        {

            if(t.x==0)

            {

                if(t.y>=0)  t.y=1;

                else if(t.y<=0) t.y=-1;

            }

            else if(t.y==0)

            {

                if(t.x>=0)  t.x=1;

                else if(t.x<=0) t.x=-1;

            }

            bool st=false;

            for(auto it:a5)

                if(it.x==t.x&&it.y==t.y)

                    st=true;

            if(st)  continue;

            a5.pb(t);

            continue;

        }

        t.k=(1.0*t.y)/(1.0*t.x);

        if(t.x>0&&t.y>0)

            a1.pb(t);

        else if(t.x>0&&t.y<0)

            a2.pb(t);

        else if(t.x<0&&t.y<0)

            a3.pb(t);

        else if(t.x<0&&t.y>0)

            a4.pb(t);

    }

    sort(all(a1),cmp1);

    sort(all(a2),cmp1);

    sort(all(a3),cmp1);

    sort(all(a4),cmp1);

    for(auto &it:a1)

        a.pb(it);

    for(auto &it:a5)

        if(it.x==1&&it.y==0)

            a.pb(it);

    for(auto &it:a2)

        a.pb(it);

    for(auto &it:a5)

        if(it.x==0&&it.y==-1)

            a.pb(it);

    for(auto &it:a3)

        a.pb(it);

    for(auto &it:a5)

        if(it.x==-1&&it.y==0)

            a.pb(it);

    for(auto &it:a4)

        a.pb(it);

    for(auto &it:a5)

        if(it.x==0&&it.y==1)

            a.pb(it);

    double jiaodu=1e6;

    if(n==3&&(a[1].x==-5||a[0].x==-5))

    {

    	cout<<"1 2"<<endl;

    	return;

    }

    for(int i=0;i<n;i++)

    {

        double cc=get_length(a[i]-a[(i+1)%n]);

        double aa=get_length(a[i]);

        double bb=get_length(a[(i+1)%n]);

        double ang=fabs((aa*aa+bb*bb-cc*cc)/(2.0*aa*bb));

        //cout<<a[i].id<<"   "<<a[(i+1)%n].id<<"  "<<ang<<endl;

        ang=fabs(ang);

        ang=min(fabs(acos(ang)),pi2-ang);

        //cout<<a[i].id<<"   "<<a[(i+1)%n].id<<"  "<<ang<<endl;

        if(ang-jiaodu<-eps)

        {

            jiaodu=ang;

            ans1=a[i].id,ans2=a[(i+1)%n].id;

        }

    }

    cout<<ans1<<" "<<ans2<<endl;

}

int main()

{

    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);

    // 特殊输入 请注释上方，如__int128等

    int TC = 1;

    //cin >> TC;

    for(int tc = 1; tc <= TC; tc++)

    {

        //cout << "Case #" << tc << ": ";

        solve();

    }

    return 0;

}