T1:Maximum Multiple

题意:第一题题意就是找三个数,加起来是n同时也是n的因子。。。

分析:

那么易得有:

  • 1=1/3+1/3+1/3
  • 1=1/2+1/4+1/4
  • 1=1/2+1/3+1/6

由于第三个n要是6的倍数,同时那么它也是三的倍数。。。但又不如三来的大,所以第三条舍去,我们直接判断前两条就好了。。。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e6+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
	template inline void read(tp &x)
	{
		x=0; register char c=getchar(); register bool f=0;
		for(;c'9';f|=(c=='-'),c = getchar());
		for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
		if(f) x=-x;
	}
	template inline void write(tp x)
	{
		if (x==0) return (void) (putchar('0'));
		if (x<0) putchar('-'),x=-x;
		LL pr[20]; register LL cnt=0;
		for (;x;x/=10) pr[++cnt]=x%10;
		while (cnt) putchar(pr[cnt--]+'0');
	}
	template inline void writeln(tp x)
	{
		write(x);
		putchar('\n');
	}
}
using namespace FastIO;
int T,n;
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        if(n%3==0) writeln(1LL*(n/3)*(n/3)*(n/3));
        else if(n%4==0) writeln(1LL*(n/2)*(n/4)*(n/4));
        else printf("-1\n");
    }
    return 0;
}

T2:Balanced Sequence

题意:给你n个只有左右括号的字符串,问你把他们拼起来最多有多少匹配的。。。

分析:写一个排序处理一下,然后玄学合并一下就好了。。。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct node
{
    int l,r;
    bool operator  c.l || (l == c.l && r < c.r);
    }
}a[N];
char s[N];

int n, cur;
int main(void)
{
    int T;
    scanf("%d", &T);
    while (T --)
    {
        scanf("%d", &n);cur=0;
        int suml = 0, sumr = 0 ,ans =0;
        for (int i = 1; i = r2) tmpl += l1 - r2;
                else tmpr += r2 - l1;
                a[i + 1].l = tmpl;
                a[i + 1].r = tmpr;
            }
            else
            {
                ans += min(r1, l2) * 2;
                int tmpl = l1, tmpr = r2;
                if (l2 >= r1) tmpl += l2 - r1;
                else tmpr += r1 - l2;
                a[i + 1].l = tmpl;
                a[i + 1].r = tmpr;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

T3:Triangle Partition

题意:是给你3×n个点,请把他们连成n个三角形。。。保证没有三点共线。。。

分析:那么我们直接按照x轴排序,然后直接扔上去,最靠左的三个连起来一定对。。。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e3+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
	template inline void read(tp &x)
	{
		x=0; register char c=getchar(); register bool f=0;
		for(;c'9';f|=(c=='-'),c = getchar());
		for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
		if(f) x=-x;
	}
	template inline void write(tp x)
	{
		if (x==0) return (void) (putchar('0'));
		if (x<0) putchar('-'),x=-x;
		LL pr[20]; register LL cnt=0;
		for (;x;x/=10) pr[++cnt]=x%10;
		while (cnt) putchar(pr[cnt--]+'0');
	}
	template inline void writeln(tp x)
	{
		write(x);
		putchar('\n');
	}
}
using namespace FastIO;
int T, n;
struct point
{
    int x,y,id;
    friend bool operator < (point a, point b){return (a.x!=b.x)?a.x<b.x:a.y<b.y;}
}a[N*4];
signed main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i = 1; i <= 3 * n; i++)
            read(a[i].x),read(a[i].y),a[i].id = i;
        sort(a+1,a+1+3*n);
        for(int i = 1; i <= 3 * n; i += 3)
            printf("%d %d %d\n",a[i].id,a[i+1].id,a[i+2].id);
    }
    return 0;
}

T4:Distinct Values

题意:给你一个数n表示数组的长度,然后给你m个区间,表示 li 到 ri
之间没有重复的数字,然后输出字典序最小的一种可能。。。

分析:暴力一点的方法是直接用map或者set存。。。然后我写了一个n^2的被×了,超级尴尬。。。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO 
{
    template inline void read(tp &x) 
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x) 
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x) 
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T, n, m, Clear, Right, ans[N];
struct node
{
    int l, r;
    friend bool operator < (node x, node y){return (x.l != y.l) ? x.l < y.l : x.r < y.r; }
}a[N];
set G;
signed main()
{
    read(T);
    while(T--)
    {
        read(n),read(m);
        Clear = Right = 0;
        G.clear();
        for(int i = 1; i <= n; i++) ans[i] = 0, G.insert(i);
        for(int i = 1; i <= m; i++)
            read(a[i].l),read(a[i].r);
        sort(a + 1, a + 1 + m);
        for(int i = 1; i  a[i].r) continue;
            for(int j = Clear; j < a[i].l; j++) if(ans[j])
                G.insert(ans[j]);
            set::iterator it = G.begin();
            for(int j = max(a[i].l, Right + 1); j <= a[i].r; j++)
            {
                ans[j] = *(G.begin());
                G.erase(G.begin());
            }
            Clear = a[i].l; Right = a[i].r;
        } 
        for(int i = 1; i <= n; i++)
        {
            if(ans[i]) printf("%d%c", ans[i],i==n?'\n':' ');
            else printf("1%c",i==n?'\n':' ');
        }
    }
    return 0;
}

T7:Chiaki Sequence Revisited

题意:

你现在出要关注这样一个序列,其通项公式为:
a[n]=1 n=1,2
a[n]=a[n-a[n-1]]+a[n-1-a[n-2]] n>2

题解:

用dls的话来讲,这题应该先上oeis。
不过其实打个表也挺好。表长这样:
1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 9 10 10 11 12 12 12 13 14 14 15 16 16 16 16 16
第一眼看上去可能和lowbit有关,事实上……一般般吧。
容易发现,如果xk个因子2,它在整个序列中就出现了k+1次。
根据序列的单调性,我们的可以二分。二分位置n是什么数。事实上check非常好写。
尽管这样,复杂度将会达到O(T(logn)^2),面临着被卡的风险。我们还是先考虑如何计算出答案。
我们知道了位置n上面是什么数,假设是k。那么我们也知道前k-1个数分别出现的次数,我们就可以用等差数列计算贡献答案。这个复杂度也是O(logn)的。
由于现在复杂度还有点紧,瓶颈在于二分位置n上是什么数。实际上,观察一下数列,然后略微做一点数学分析,就不难知道了k在区间[n/2,n/2+logn]之间浮动。这样缩小了二分范围,复杂度就变成了O(Tlogn*loglogn),可以跑得飞快了。

#pragma GCC optimize(2)
#include#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int mo=1e9+7;
ll n;
ll exam (ll k,ll ret=1) {
    ll t=k;
    for ( ; t; t>>=1) ret+=t;
    return ret;
}
ll reply (ll n,ll k,ll w,ll ret=1) {
    ll t,s,ls,lls;
    for (t=1; t<=k; t1,ls=ls+1;
        else lls=ls,ls=(ls+1)>>1;
        s=(lls%mo)*(ls%mo)%mo;
        s=s*(t%mo)%mo,ret=(ret+s)%mo;
    }
    ret=(ret+((n-w)%mo+mo)*(k%mo))%mo;
    return ret;
}
int main () {
    int T; cin>>T;
    for ( ; T; --T) {
        scanf("%lld",&n);
        if (n==1) puts("1"); else
        if (n==2) puts("2"); else
        if (n==3) puts("4"); else {
            ll l=n/2-1,r=n/2+61,mid,t1,t2,k,t;
            while (l>1;
                t1=exam(mid),t2=exam(mid+1);
                if (t1<n&&n=n) r=mid-1; else l=mid+1;
            }
            printf("%lld\n",reply(n,k,t)%mo);
        }
    }
    return 0;
}

T11:Time Zone

题意:给出一个时间,然后在给你几个时间点,让你把他们转化到第一个时间线上。。。

分析:直接转化成分钟算就好了

 

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO 
{
    template inline void read(tp &x) 
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x) 
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x) 
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n,a,b;
char c;
double d;
int main()
{
    read(n);
    for(int i=0;i<n;++i)
    {
        scanf("%d %d UTC%c%lf",&a,&b,&c,&d);
        int tim=a*60+b;if(c=='-')d=-d+24;
        int tmp=(d*10-80)*6;
        if(tmp<0)tmp+=1440;
        tim=(tim+tmp)%1440;
        printf("%.02d:%.02d\n",tim/60,tim%60);
    }
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注