3532. 热河路

题面 统计数据 讨论
madmax
4 年，4 月前

说实话，靠I/O卡时间真的有意义吗

回复
10152510300
6 年，4 月前

第十个点一直RE？

回复
13627999316
4 年，8 月前

脑子转不过弯的蠢B只会hash+模拟

#include <iostream>
using namespace std;
const int maxn = 1e9+5;
bool a[maxn]={false};

int main() {
    int n,temp;
    scanf("%d",&n);

    int cnt = 0;    //¼ä¸ôΪ1 
    for(int i = 1;i <= maxn;i+=cnt) {
        a[i] = 1;
        cnt++;
    }

    while(n--) {
        scanf("%d",&temp);
        printf("%d\n",a[temp]);
    }
    return 0;
}
回复
upper1027
6 年，3 月前

cin慢是有原因的，其实默认的时候，cin与stdin总是保持同步的，也就是说这两种方法可以混用，而不必担心文件指针混乱，同时cout和stdout也一样，两者混用不会输出顺序错乱。正因为这个兼容性的特性，导致cin有许多额外的开销，如何禁用这个特性呢？只需一个语句std::ios::sync_with_stdio(false);，这样就可以取消cin于stdin的同步了。

回复
Kuroko
5 年，8 月前

感谢大佬，成功ac了

回复
我太难了
4 年，8 月前

找规律喽

include

include

int main()
{
int i,t;
scanf(“%d”,&t);
for (i=0;i<t;i++){
int n;
scanf(“%d”,&n);
n=(n-1)2;
int b=sqrt(n);
if (b(b+1)==n) printf(“1\n”);
else printf(“0\n”);
}
return 0;
}

回复
mansoup
4 年，10 月前

//类似公务员考试找规律

include

using namespace std;
//被迫用C？
int main(){
int N;
scanf(“%d”,&N);
while(N–){
int num;
scanf(“%d”,&num);
if(num==1){
printf(“1\n”);
continue;
}
num–;
int i=sqrt(num<<1);
if((i*(i+1))>>1==num){//右移动比除法快
printf(“1\n”);
}else{
printf(“0\n”);
}
}
}

回复
lawson
4 年，10 月前

你好，请问你的代码中的这个左移与右移的原理是什么啊？

回复
mansoup
4 年，10 月前

看0和1的规律，两个1之间的0每次增加1个，等差数列公式 (/2)=>(>>)！

回复
圣墓山花哩喵
3 年，6 月前

include

using namespace std;
int main()
{
int T;
cin >> T;
for(int t = 0;t < T;t = t + 1)
{
double pos;
scanf(“%lf”,&pos);
int temp = sqrt(8pos - 7);
if(temp * temp == 8pos - 7 && temp % 2 == 1)
printf(“1\n”);
else
printf(“0\n”);
}
}

回复
Lucas
5 年，6 月前

//贴出另一种解法，想法来源于实际生产中更愿意用空间换时间

include

include

//#include

define mMax 1000000010

using namespace std;

bool add[mMax]={false};
int n;
int que; //question

int main()
{
int tmp=1,i=1;
while(tmp<mMax)
{
add[tmp]=true;
tmp+=i;
i++;
}
while(scanf(“%d”,&n)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf(“%d”,&que);
if(add[que]==true)printf(“1\n”);
else printf(“0\n”);
//fflush(stdout);
}
}
return 0;
}

回复
parker
4 年，1 月前

被迫C (狗头.jpg)
cin cout改成scanf printf就好了!

include

include

using namespace std;
int main() {
std::ios::sync_with_stdio(false);
int n; cin >> n;
for (int i = 0; i < n; ++i) {
int a;
scanf(“%d”, &a);
a = 2 * (a - 1);
int A = a;
a=sqrt(a);
if (a*(a + 1) == A)
printf(“1\n”);
else
printf(“0\n”);
}
return 0;
}

回复
jackqi
4 年，7 月前

开了2个hash直接不超时了，只要map开得多时间就追不上我
int main()
{//ios::sync_with_stdio(false);

ifdef ONLINE_JUDGE

else

freopen("1.txt", "r", stdin);

endif

//ios::sync_with_stdio(false);
vectorv;
long long int c=1;
mapmp;
mapmp1;
for(long long int i=1;i<=int(1e9);i+=c++)
{
v.push_back(i);
if(i<=5int(1e8)) mp[i]=1;
else mp1[i]=1;
}
int n;
cin>>n;
for(int i=0;i<n;i++)
{ long long int t;
scanf(“%lld”,&t);
if(t<=5int(1e8)){
if(mp[t]) printf(“%d\n”,1);
else printf(“%d\n”,0);
}
else{if(mp1[t]) printf(“%d\n”,1);
else printf(“%d\n”,0);

}
}
return 0;
}

回复
helloworldyy
4 年，2 月前

我服了。。用c++的输入输出第十个点就超时，用c的输入输出就不超时了。。。

include

include

using namespace std;
int main(){
string str1=”1”,str2=”1”;
int i,n,index;
scanf(“%d”,&n);
for(i=0;i=index)
printf(“%c\n”,str1[index-1]);
else{
do{
str2+=”0”;
str1+=str2;
}while(str1.size()<index);
printf(“%c\n”,str1[index-1]);
}
}
return 0;
}

回复
10175101178
6 年，2 月前

第10个点一直都是runtime error求指教一下

include

using namespace std;
typedef long long ll;
int main()
{
ll t,p;
cin>>t;
while(t–)
{
cin>>p;

    double x=(1+sqrt(1.0+8.0*(p-1)))/2.0;
              if(x-(ll)x==0)
              cout<<"1"<<endl;
              else
                  cout<<"0"<<endl;

    }

}

回复
柴柴柴拆柴柴
4 年，10 月前

初等数学题

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

double solution(long n);
long mysum(long n);

int main(void)
{
    int *anslst;
    long *queslst;
    int i,cases;
    double mysolution;

    scanf("%d",&cases);
    anslst=(int*)malloc(cases*sizeof(int));
    queslst=(long*)malloc(cases*sizeof(long));

    for(i=0;i<cases;i++)
        scanf("%ld",&queslst[i]);
    for(i=0;i<cases;i++)
    {
        mysolution=solution(queslst[i]);
        if(mysolution-(long)mysolution==0)
        {
            anslst[i]=0;
        }
        else
        {
            if(queslst[i]-mysum((long)mysolution)==1)
                anslst[i]=1;
            else
                anslst[i]=0;
        }
    }

    for(i=0;i<cases;i++)
        printf("%d\n",anslst[i]);

    free(anslst);
    free(queslst);

    return 0;
}

double solution(long n)
{
    double result;
    result=(-1.0+sqrt(1+8.0*n))/2.0;

    return result;
}

long mysum(long n)
{
    return (n+1)*n/2;
}
回复
heliangda
4 年，9 月前

有用python过的同学吗？
times = eval(input())
for i in range(times):
index =eval(input())
q = (index-1) 2
p =int(pow(q,0.5))
if q == p(p+1):
print(1)
else:
print(0)

我这代码还有什么地方可以优化？最后1500000条数据超时了。

回复
Commando
2 年，11 月前

不加第一句ios::sync_with_stdio(false);第十个测试点就会RE，什么鬼

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);

    constexpr ull inf = 1e9;
    int n;
    cin >> n;
    unordered_map<ull, bool> hashmap;
    for (ull i = 1, j = 1; i <= inf; i += j, ++j) {
        hashmap[i] = true;
    }
    while (n--) {
        ull a, res;
        cin >> a;
        res = hashmap[a] ? 1 : 0;
        cout << res << endl;
    }
}
回复
Commando
2 年，11 月前

确实换成C输入输出就没这毛病

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;

int main() {
    constexpr ull inf = 1e9;
    int n;
    scanf("%d", &n);
    unordered_map<ull, bool> hashmap;
    for (ull i = 1, j = 1; i <= inf; i += j, ++j) {
        hashmap[i] = true;
    }
    while (n--) {
        int a;
        scanf("%d", &a);
        printf("%d\n", hashmap[a] ? 1 : 0);
    }
}
回复
Mr.Robot
3 年，8 月前

C++程序跑的慢，相同的算法转成C就能过了

回复
TechAoba
4 年，10 月前

题目中数据量较大，我用了快读。开始想到用hash表来做，但是不太熟悉，于是直接开根号再判断，算式是等差公式。
int read() {
bool flag = false;
int num = 0;
char c = getchar();
while((c<‘0’ || c>‘9’ )&& c!=’-‘) c = getchar();
if(c==’-‘) flag = true, c = getchar();
while(c>=‘0’ && c<=‘9’) num = (num<<3) + (num<<1) + (c^48), c = getchar();
return flag?-num:num;
}

int main()
{
int n = read(), a, t;
while(n–) {
a = read();
t = (a-1)2;
t = (int)sqrt(t);
//cout<<”t是”<<t<<endl;
if((t+1)t/2+1==a) printf(“1\n”);
else printf(“0\n”);
}
return 0;
}

回复
Irisiscool
4 年，1 月前

xdm有用Java过的吗..

回复
YZAZJL
4 年，9 月前

简直无法理解，用c++的输入会超时，用c的输入语法不会超时，感觉学无止境

回复
YZAZJL
4 年，9 月前

再补充一个问题，这个地方为啥不用long long？用int不是不能表达这么大的数么？好奇

回复
liujieaaa
3 年，8 月前

C中int类型是32位的,范围是-2147483648到2147483647

回复
Hairaa
4 年，8 月前 
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int num;
        scanf("%d",&num);
        int n = sqrt((num-1)*2);
        if (n*(n + 1) == (num-1)*2 || n * (n - 1) == (num-1)*2) { printf("%d\n",1); }
        else { printf("%d\n", 1); }
    }
    return 0;
}
回复
10175101178
6 年，2 月前

看了一楼指导，更改了代码成功AC了

include

using namespace std;
typedef long long ll;
int main()
{
ll t,p;
std::ios::sync_with_stdio(false);
std::cin>>t;
while(t–)
{std::cin>>p;
double x=(1+sqrt(1.0+8.0*(p-1)))/2.0;
if(x-(ll)x==0)
cout<<”1”<<endl;
else
cout<<”0”<<endl;

    }

}

回复
Kevin_K
6 年，4 月前
Hints:

cin->RE.

回复
Fifnmar
4 年，11 月前

我发现第十个点一个个试会TLE，所以用了二分法。

#include <cstdio>

inline unsigned get_uint() {
    unsigned ans = 0;
    signed char ch = getchar();
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9') {
        ans = ans * 10 + ch - '0';
        ch = getchar();
    }
    return ans;
}

void solve(int k, int bg, int ed) {
    int mid = (bg + ed) / 2;
    if (mid * (mid + 1) / 2 < k) {
        solve(k, mid + 1, ed);
        return;
    }
    if (k <= mid * (mid - 1) / 2) {
        solve(k, bg, mid);
        return;
    }
    if (k == mid * (mid - 1) / 2 + 1)
        printf("1\n");
    else
        printf("0\n");
}

int main() {
    unsigned n = get_uint();
    for (int i = 0; i < n; ++i) {
        unsigned k = get_uint();
        solve(k, 1, 44722);
    }
}
回复
你当前正在回复 博客/题目
存在问题！

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn