Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 240 words)

hdu 4135 Co-prime 容斥原理

hdu 4135

具有教科书性质的容斥原理应用实例。
能不重复、不遗漏地选出所有合数，也就能得到质数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/** Aug 26, 2015 9:40:09 PM
 * PrjName:hdu4135
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static int maxn=1001;
    static int[] pri,fstp;
    static Vector<Integer> vec=new Vector<Integer>();
    static void get_prime(){
        pri=new int[maxn];
        fstp=new int[maxn];
        for(int i=2;i<maxn;i++){
            if (fstp[i]==0){
                pri[++pri[0]]=i;
            }
            for(int j=1;j<=pri[0]&&i*pri[j]<maxn;j++){
                int k=i*pri[j];
                fstp[k]=pri[j];
                if (i%pri[j]==0)
                    break;
            }
        }
    }
    static Vector<Integer> get_prime_factor(int n){
        Vector<Integer> res=new Vector<Integer>();
        res.clear();
        for(int i=1;i<=pri[0]&&pri[i]*pri[i]<=n;i++)
            if (n%pri[i]==0){
                res.add(pri[i]);
                while(n%pri[i]==0)
                    n/=pri[i];
            }
        if (n>1) res.add(n);
        return res;
    }
    static long solve(long n,Vector<Integer> vec){
        long res=0L;
        final int m=vec.size();
        for(long i=1L;i<(1L<<m);i++){
            boolean tag=false;
            long tmp=1L;
            for(int j=0;j<m;j++)
                if (((1L<<j)&i)>0){
                    tag^=true;
                    tmp*=vec.get(j).longValue();
                }
            res+=tag?n/tmp:-n/tmp;
        }
        return n-res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        get_prime();
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            long a=in.nextLong();
            long b=in.nextLong();
            int n=in.nextInt();
            vec=get_prime_factor(n);
            out.println("Case #"+(++cas)+": "+(solve(b,vec)-solve(a-1,vec)));
        }
        out.flush();
        out.close();
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 531 words)

2013 ACM/ICPC Asia Regional Chengdu Online

1007 F(x)数位DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/** Aug 22, 2015 5:23:42 PM
 * PrjName:hdu4734
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static int[][] f;
    static int[] digit;
    final static int maxm=4600;
    static int fun(int n){
        int res=0,tmp=1;
        while(n>0){
            res+=n%10*tmp;
            tmp<<=1;
            n/=10;
        }
        return res;
    }
    static void init(){
        int tmp=1;
        f=new int[10][maxm+1];
        f[0][0]=1;
        for(int i=1;i<10;i++){
            for(int j=0;j<=maxm;j++)
                for(int k=0;k<=9;k++)
                    if (j+tmp*k<=maxm)
                        f[i][j+tmp*k]+=f[i-1][j];
            tmp<<=1;
        }
        for(int i=0;i<10;i++)
            for(int j=1;j<=maxm;j++) f[i][j]+=f[i][j-1];
    }
    static int[] getdg(int n){
        int[] res=new int[10];
        while(n>0){
            res[++res[0]]=n%10;
            n/=10;
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        init();
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int A=in.nextInt();
            int B=in.nextInt();
            int m=fun(A);
            digit=getdg(B);
            int ans=0,tmp=1<<digit[0];
            for(int i=digit[0];i>=1;i--){
                tmp>>=1;
                for(int k=0;k<digit[i];k++){
                    
                    if (m-k*tmp>=0){
                        ans+=f[i-1][m-k*tmp];
                    }
                }
                m-=digit[i]*tmp;
                if (m<0) break;
                
            }
            if (m>=0) ans++;
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

磕磕绊绊的，到底有几大难？
期初是有过转化为背包问题的尝试，但是忽视了数位DP的处理手段；可先扩大枚举范围，再从中筛选。
预处理的两套循环不能杂糅在一起，因为先通过递推求了第i位、限制F(x)==j的解，然后才相加得到第i位、限制F(x)≤j的解。
筛选时注意“小于”的枚举方式。
最后还应留意B为可行解的条件。

1010 A Bit Fun

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/** Aug 22, 2015 4:28:18 PM
 * PrjName:hdu4737
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static int[] a;
    static Queue<Integer> que=new LinkedList<Integer>();
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        while(T-->0){
            int n=in.nextInt();
            int m=in.nextInt();
            a=new int[n+1];
            que.clear();
            int ans=0;
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                int k=que.size();
                for(int j=0;j<k;j++){
                    int tmp=que.poll()|a[i];
                    if (tmp<m) que.add(tmp);
                }
                if (a[i]<m) que.add(a[i]);
                ans+=que.size();
            }
            out.println("Case #"+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

并没有实现有些题解中所说的O(nlogn)或O(30n)的算法，但总的运行时间还是较短的？

Posted Updated  Semprathlon / Simfae Dean OSa few seconds read (About 87 words)

OS X下的一些个性化设置

defaults write com.apple.screencapture location /path/

killall SystemUIServer

  • Finder显示隐藏文件

defaults write com.apple.finder AppleShowAllFiles -bool true

  • Finder显示全部驱动器
Screen Shot 2015-08-23 at 11.15.30
  • Dashboard不显示为单独页面
Screen Shot 2015-08-23 at 11.17.10
  • 调整屏幕亮度等常用功能快捷键
Screen Shot 2015-08-23 at 11.18.34
  • 允许未知来源Application的运行
Screen Shot 2015-08-23 at 11.20.43 Screen Shot 2015-08-23 at 11.20.59
  • 管理开机启动项

Snip20151103_3

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 338 words)

BestCoder

1001 Victor and Machine

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

  • Problem Description
    Victor has a machine. When the machine starts up, it will pop out a ball immediately. After that, the machine will pop out a ball every w seconds. However, the machine has some flaws, every time after x seconds of process the machine has to turn off for y seconds for maintenance work. At the second the machine will be shut down, it may pop out a ball. And while it’s off, the machine will pop out no ball before the machine restart.
    Now, at the 0 second, the machine opens for the first time. Victor wants to know when the n-th ball will be popped out. Could you tell him?

  • Input
    The input contains several test cases, at most 100 cases.
    Each line has four integers x, y, w and n. Their meanings are shown above。
    $ 1\leq x,y,w,n\leq 100 $ .

  • Output
    For each test case, you should output a line contains a number indicates the time when the n-th ball will be popped out.

  • Sample Input
    2 3 3 3
    98 76 54 32
    10 9 8 100

  • Sample Output
    10
    2664
    939

n-1的问题，自己刚开始出了点差错：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/** Aug 22, 2015 7:03:37 PM
 * PrjName:Bc52-01
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
        PrintWriter out=new PrintWriter(System.out);
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int x=(int)in.nval;
            in.nextToken();
            int y=(int)in.nval;
            in.nextToken();
            int w=(int)in.nval;
            in.nextToken();
            int n=(int)in.nval;
            if (n==1){
                out.println(0);continue;
            }
            if (w>x){
                out.println((n-1)*(x+y));continue;
            }
            else if (w==x){
                out.println((n-1)/2*(x+y)+(n-1)%2*x);continue;
            }
            else{
                int tmp=(x+w)/w;
                out.println((n-1)/tmp*(x+y)+(n-1)%tmp*w);continue;
            }
        }
        out.flush();
        out.close();
    }

}
Posted Updated  Semprathlon / Simfae Dean OS8 minutes read (About 1213 words)

暑假翻江倒海折腾Clover+Mac险遭失败

重大突破！
基本硬件信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
主板:
  处理器名称                                        Mobile DualCore Intel Core i5-2450M, 2900 MHz (29 x 100)
  主板名称                                          Hewlett-Packard HP ProBook 4431s
  主板芯片组                                        Intel Cougar Point HM65, Intel Sandy Bridge
  系统内存                                          8119 MB  (DDR3-1600 DDR3 SDRAM)
  BIOS 类型                                         Compaq (05/23/2012)

显示设备:
  显示适配器                                        Intel(R) HD Graphics 3000  (2108 MB)
  3D 加速器                                         AMD Radeon HD 6490M (Seymour)
  3D 加速器                                         Intel HD Graphics 3000

多媒体:
  音频适配器                                        IDT 92HD87B1/3 @ Intel Cougar Point PCH - High Definition Audio Controller [B-2]
  音频适配器                                        Intel Cougar Point HDMI @ Intel Cougar Point PCH - High Definition Audio Controller [B-2]

存储设备:
  硬盘驱动器                                        TOSHIBA MQ01ABD050 SCSI Disk Device  (500 GB, 5400 RPM, SATA-II)
  光盘驱动器                                        hp DVDRAM GT50N SCSI CdRom Device  (DVD+R9:6x, DVD-R9:6x, DVD+RW:8x/8x, DVD-RW:8x/6x, DVD-RAM:5x, DVD-ROM:8x, CD:24x/24x/24x DVD+RW/DVD-RW/DVD-RAM)


输入设备:
  键盘                                              PS/2 标准键盘
  鼠标                                              HID-compliant mouse
  鼠标                                              Logitech HID-compliant Unifying Mouse
  鼠标                                              PS/2 兼容鼠标

网络设备:
  网络适配器                                        Microsoft Virtual WiFi Miniport Adapter #2
  网络适配器                                        Qualcomm Atheros AR9285 802.11b/g/n WiFi Adapter  
  网络适配器                                        Realtek PCIe GBE Family Controller

外围设备:
  USB2 控制器                                       Intel Cougar Point PCH - USB EHCI #1 Controller [B-2]
  USB2 控制器                                       Intel Cougar Point PCH - USB EHCI #2 Controller [B-2]
  USB3 控制器                                       NEC uPD720200AF1 USB 3.0 Host Controller
  USB 设备                                          2.4G Wireless headset
  USB 设备                                          Generic Bluetooth Adapter
  USB 设备                                          HP HD Webcam [Fixed]
  USB 设备                                          Logitech Unifying USB receiver
  USB 设备                                          USB Composite Device
  USB 设备                                          USB Input Device (Logitech Download Assistant)
  USB 设备                                          USB 大容量存储设备
  USB 设备                                          Validity Sensor
  USB 设备                                          Wacom Tablet
  电池                                              Microsoft AC Adapter
  电池                                              Microsoft ACPI-Compliant Control Method Battery

Stage 1

在大量繁复的尝试中偶然发现，此前的系统引导失败与所使用的Clover版本有关。
现用的经尝试可成功引导的为Clover_v2k_r2482。
部署至EFI分区的EFI/Clover目录下，用CloverX64.efi替换EFI/Boot/下的bootx64.efi，将原有的EFI/Microsoft文件夹移至C:/Boot/下(注意备份原始文件)，避免系统启动时默认进入win系统。
记得删掉EFI/Clover/drivers64UEFI下csm开头的efi文件（支持CSM的显卡驱动文件），修复进入Clover是屏幕亮但无显示的故障。
IMG_5639.JPG

Stage 2

根据热门教程，将pcbeta提供的OS X Mavericks 10.9.5懒人版镜像写入hfs+分区。
但是引导进入安装分区时，菊花会无故停转，随后重启。
开启了啰嗦模式再观察报错情况。
IMG_5654-1.jpg
查阅PCBETA相关教程得知，不仅需要fakesmc.kext，更需要NullCPUPowerManagement.kext禁用（部分？）电源管理，以解决这个似是而非的蓝牙驱动报错。
附加的kext放在fakesmc的plugin目录下。
成功进入安装程序。
IMG_5658.JPG

Stage 3

完成初始设定后进入系统。
IMG_5662.JPG
在PCBETA上获取了以下kext以驱动相关硬件（极为困惑的是，不同的kext，放在合适的目录下方可生效）：

kext 硬件 存放目录
IO80211Family.kext Qualcomm Atheros AR9285 802.11b/g/n WiFi Adapter S/L/E
IOath3kfrmwr.kext Qualcomm Atheros AR3011 Bluetooth 3.0 Adapter S/L/E
IOBluetoothFamily.kext Qualcomm Atheros AR3011 Bluetooth 3.0 Adapter S/L/E
ACPIBatteryManager.kext Battery PR06047 fakesmc.kext/Plugin
GenericUSBXHCI.kext NEC uPD720200AF1 USB 3.0 Host Controller fakesmc.kext/Plugin
AppleACPIPS2Nub.kext ? fakesmc.kext/Plugin
ApplePS2Controller.kext ? fakesmc.kext/Plugin
ApplePS2Keyboard.kext 101/102-Key or MS Natural Keyboard fakesmc.kext/Plugin
ApplePS2Mouse.kext Synaptics PS/2 Port TouchPad fakesmc.kext/Plugin
RealtekRTL8111.kext Realtek RTL8168/8111 PCI-E Gigabit Ethernet Adapter fakesmc.kext/Plugin
AppleIntelSNBGraphicsFB.kext Intel HD Graphics 3000 & Intel Cougar Point HDMI S/L/E
AppleHDA.kext IDT 92HD87B1/3 @ Intel Cougar Point PCH S/L/E

Stage 4

更新了Clover的config.plist以指定开机默认启动系统，增强硬件性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
	<key>ACPI</key>
	<dict>
		<key>DSDT</key>
		<dict>
			<key>Debug</key>
			<false/>
			<key>DropOEM_DSM</key>
			<false/>
			<key>ReuseFFFF</key>
			<false/>
		</dict>
		<key>SSDT</key>
		<dict>
			<key>DropOem</key>
			<true/>
			<key>EnableC2</key>
			<true/>
			<key>EnableC4</key>
			<true/>
			<key>EnableC6</key>
			<true/>
			<key>Generate</key>
			<true/>
		</dict>
	</dict>
	<key>Boot</key>
	<dict>
		<key>Debug</key>
		<false/>
		<key>DefaultVolume</key>
		<string>OS X 10.9.5</string>
		<key>Legacy</key>
		<string>PBR</string>
		<key>Secure</key>
		<false/>
		<key>Timeout</key>
		<integer>3</integer>
		<key>XMPDetection</key>
		<false/>
	</dict>
	<key>Devices</key>
	<dict>
		<key>Audio</key>
		<dict>
			<key>Inject</key>
			<string>Detect</string>
		</dict>
		<key>FakeID</key>
		<dict>
			<key>IntelGFX</key>
			<string>0x01268086</string>
		</dict>
		<key>USB</key>
		<dict>
			<key>AddClockID</key>
			<true/>
			<key>FixOwnership</key>
			<true/>
			<key>Inject</key>
			<true/>
		</dict>
		<key>UseIntelHDMI</key>
		<true/>
	</dict>
	<key>DisableDrivers</key>
	<array>
		<string>Nothing</string>
	</array>
	<key>GUI</key>
	<dict>
		<key>Hide</key>
		<array>
			<string>\EFI\BOOT\BOOTX64.EFI</string>
			<string>Windows</string>
		</array>
		<key>Language</key>
		<string>en:0</string>
		<key>Mouse</key>
		<dict>
			<key>DoubleClick</key>
			<integer>500</integer>
			<key>Enabled</key>
			<false/>
			<key>Mirror</key>
			<false/>
			<key>Speed</key>
			<integer>0</integer>
		</dict>
		<key>Scan</key>
		<dict>
			<key>Entries</key>
			<true/>
			<key>Legacy</key>
			<true/>
			<key>Tool</key>
			<true/>
		</dict>
		<key>Theme</key>
		<string>Universe</string>
	</dict>
	<key>Graphics</key>
	<dict>
		<key>Inject</key>
		<dict>
			<key>ATI</key>
			<false/>
			<key>Intel</key>
			<false/>
			<key>NVidia</key>
			<false/>
		</dict>
		<key>NvidiaSingle</key>
		<false/>
	</dict>
	<key>KernelAndKextPatches</key>
	<dict>
		<key>AppleRTC</key>
		<true/>
		<key>AsusAICPUPM</key>
		<true/>
		<key>Debug</key>
		<false/>
		<key>KernelCpu</key>
		<false/>
		<key>KernelHaswellE</key>
		<false/>
		<key>KernelLapic</key>
		<false/>
		<key>KernelPm</key>
		<false/>
		<key>KextsToPatch</key>
		<array>
			<dict>
				<key>Comment</key>
				<string>External icons patch</string>
				<key>Find</key>
				<data>
				RXh0ZXJuYWw=
				</data>
				<key>Name</key>
				<string>AppleAHCIPort</string>
				<key>Replace</key>
				<data>
				SW50ZXJuYWw=
				</data>
			</dict>
		</array>
	</dict>
	<key>SystemParameters</key>
	<dict>
		<key>InjectKexts</key>
		<string>Detect</string>
		<key>InjectSystemID</key>
		<true/>
	</dict>
</dict>
</plist>

Stage 5

启用DSDT补丁，以便实现深层次的硬件兼容。
在不存在DSDT patch的条件下，于Clover中按F4键，快速获得BIOS中的DSDT、SSDT于目录EFI/Clover/ACPI/origin。
初次打补丁时，发现有些修正并未完全生效。
认真研读PCBETA相关教程，更正了打补丁的方式。
将SSDT-0.aml更名为SSDT.aml，去掉其余aml文件末尾的x。
在Mac中获取命令行版的iasl，在终端下对DSDT.aml、SSDT-.aml进行反编译得到.dsl。
使用maciasl，添加External(…)等行，排除了编译错误。
引用Rehebman的补丁源，针对显卡、屏幕亮度等应用了补丁。
修改完后，再在终端下将*.dsl编译为*.aml，放到EFI/Clover/ACPI/patched。
【未完待续

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga few seconds read (About 73 words)

Solving LCM【C0n,C1n, ,Cnn】

摘自《具体数学·计算机科学基础（英文版·第二版）》第5章习题及其解答：
0FF23C24-69C5-417E-BFA3-04CE6D477E87

BBACCBCF-BE37-40B5-8416-DD3FB5C6061A

$ \epsilon_p(n)$denotes the exponent of the prime p in the standard factorization of positive integer n.

$ \epsilon_p(n)$表示正整数n的因式分解中，质数p的指数。

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 466 words)

BestCoder

1001 Distribution money

WA过一发，因为忽视了金额的分布范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 2015年8月8日 下午7:02:20
 * PrjName:Bc50-01
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static int[] a;
    static int maxn=10001;
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
        PrintWriter out=new PrintWriter(System.out);
        a=new int[maxn];
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int n=(int)in.nval;
            Arrays.fill(a, 0);
            for(int i=1;i<=n;i++){
                in.nextToken();
                int k=(int)in.nval;
                a[k]++;
            }
            int ans=-1;
            for(int i=0;i<maxn;i++)
                if ((a[i]<<1)>n)
                    ans=i;
            //if (n>1)
                out.println(ans);
            //else 
                //out.println(-1);
        }
        out.flush();
        out.close();
    }
}

1002 Run

明显搞复杂了，做了一回出题人眼中的“火星人”T_T
平面上的整点就是无法构成正三角形、正五边形、正六边形，没这点见识就只有瞎弄。。。
简化到这个地步，正方形的判断就应该仔细点了吧？四条边及两对角线的长度比较都写上， 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Nov 19, 2015 7:32:18 PM
 * PrjName: hdu5365
 * @semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static Point[] pt;
    static boolean check(Point p1,Point p2,Point p3,Point p4){
        double[] v=new double[6];
        v[0]=Point.dist(p1, p2);
        v[1]=Point.dist(p2, p3);
        v[2]=Point.dist(p3, p4);
        v[3]=Point.dist(p1, p4);
        v[4]=Point.dist(p1, p3);
        v[5]=Point.dist(p2, p4);
        Arrays.sort(v);
        return v[0]==v[1]&&v[1]==v[2]&&v[2]==v[3]&&v[4]==v[5];
    }
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        while(in.nextLine()!=null){
            int n=in.nextInt();
            pt=new Point[n];
            for(int i=0;i<n;i++)
                pt[i]=new Point(in.nextInt(), in.nextInt());
            int ans=0;
            for(int i=0;i<n;i++)
                for(int j=i+1;j<n;j++)
                    for(int k=j+1;k<n;k++)
                        for(int l=k+1;l<n;l++){
                            Point p1=pt[i],p2=pt[j],p3=pt[k],p4=pt[l];
                            if (check(p1, p2, p3, p4))
                                ans++;
                        }
            out.println(ans);
        }
        out.flush();
        out.close();
    }
}

1003 The mook jong

多么有教育意义的猜公式，猜不出就别偏执了。。。
f[i]=s[i-3]+1,s[i]=s[i-1]+f[i],…

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 467 words)

Bestcoder

1001 Untitled

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 2015年8月1日 下午7:15:14
 * PrjName:Bc49-01
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static ArrayList<Integer> v=new ArrayList<Integer>();
    static int[] a,f;
    static int lowbit(int x){
        return x&(-x);
    }
    static int get(int x){
        int res=0;
        while(x>0){
            res++;
            x-=lowbit(x);
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            v.clear();
            int n=in.nextInt();
            int m=in.nextInt();
            for(int i=1;i<=n;i++)
                v.add(in.nextInt());
            Collections.sort(v);
            f=new int[1<<n];
            Arrays.fill(f, -1);
            f[0]=m;
            //out.println(n);
            int ans=Integer.MAX_VALUE;
            for(int i=0;i<(1<<n);i++)
                if (f[i]>0)
                    for(int j=0;j<n;j++)
                        if (((1<<j)&i)==0){
                            int k=i|(1<<j);
                            f[k]=f[i]%v.get(j);
                            if (f[k]==0)
                                ans=Math.min(ans, get(k));
                        }
            if (ans==Integer.MAX_VALUE) out.println(-1);
            else out.println(ans);
        }
        out.flush();
        out.close();
    }
}

1002 Three Palindromes

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

  • Problem Description
    Can we divided a given string S into three nonempty palindromes?

  • Input
    First line contains a single integer $ T \leq 20 $ which denotes the number of test cases.
    For each test case , there is an single line contains a string S which only consist of lowercase English letters. $ 1\leq |s| \leq 20000 $

  • Output
    For each case, output the “Yes” or “No” in a single line.

  • Sample Input
    2
    abc
    abaadada

  • Sample Output
    Yes
    No

赛时的Hash做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * 2015年8月1日 下午7:47:15
 * PrjName:Bc49-02
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static long pri=29L;
    static long lh(String s,long res,int p){
        return res*pri+(long)(s.charAt(p)-'a');
    }
    static long rh(String s,long res,int p,long m){
        return res+(long)(s.charAt(p)-'a')*m;
    }
    static BitSet v=new BitSet(20010);
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            String s=new String(in.next());
            int len=s.length();
            //s=s+"#"+(new StringBuffer(s).reverse().toString());
            //out.println(s);
            boolean ans=false;
            long l1=0L,r1=0L,tmp=1L;
            for(int i=0;i<len;i++){
                if (ans) break;
                l1=lh(s, l1, i);
                r1=rh(s, r1, i, tmp);
                //out.println(i+" "+l1+" "+r1);
                tmp*=pri;
                //if ((i&1)>0) continue;
                if (l1==r1){
                    //out.println("f"+i);
                    long l2=0L,r2=0L,tmp2=1L;
                    v.clear();
                    for(int j=i+1;j<len;j++){
                        l2=lh(s,l2,j);
                        r2=rh(s,r2,j,tmp2);
                        tmp2*=pri;
                        //if (((j-i+1)&1)>0) continue;
                        if (l2==r2) v.set(j);
                    }
                    
                    l2=0L;r2=0L;tmp2=1L;
                    for(int j=len-1;j>i;j--){
                        l2=lh(s,l2,j);
                        r2=rh(s,r2,j,tmp2);
                        tmp2*=pri;
                        //if (((len-j+1)&1)>0) continue;
                        if (l2==r2&&v.get(j-1)){
                            ans=true;break;
                        }
                    }
                }
            }
            out.println(ans?"Yes":"No");
        }
        out.flush();
        out.close();
    }
}

首次尝试去hack别人不成，还被人黑了，立马TLE

题解介绍的多种方法中，个人认为二分+hash代码量较少，如何实现？

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 156 words)

2015 Multi-University Training Contest 5

1009 MZL’s Border

字符串是可递归形式构造的，求解也是递归的；
但是递归时划分的三种情况，最终并没有做好化归 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
    static BigInteger f[] = new BigInteger[1005];
    public static void main(String[] args){
        f[1] = new BigInteger("1");
        f[2] = new BigInteger("2");
        for(int i = 3; i <= 1001; i++)
            f[i] = f[i - 1].add(f[i - 2]);
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        int n;
        BigInteger m;
        for(int cas = 1; cas <= T; cas++){
            n = cin.nextInt();
            m = cin.nextBigInteger();
            BigInteger mm = m.add(new BigInteger("1"));
            int p = 0;
            for(int i = 1; i <= 1001; i++){
                if(f[i].compareTo(mm) > 0){
                    p = i;
                    break;
                }
            }
            BigInteger ans = m.subtract(f[p - 2]);
            System.out.println(ans.mod(new BigInteger("258280327")));
        }
        
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 436 words)

2015 Multi-University Training Contest 4

1009 Walk Out

状态压缩方面，虽然想到了用一维的x+y替代二维的x,y，但并没有做到位。
既然可以转化成二维DP，还有何搜索必要
寻找合适的出发点时，不要陷入“极近点”而丢失了“最近点”！ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<cctype>

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int inf=0x7fffffff;
const double eps=1e-3;

typedef pair<int,int> pr;
const int dir[4][2]={ {0,-1},{0,1},{-1,0},{1,0}};
const int maxn=1010;
const int maxm=1010;
int n,m,X0,Y0;
bool g[maxn][maxm],f[maxn][maxm],vis[maxn][maxm];
char str[maxn];

bool can(int x,int y){
    if (x<1||x>n||y<1||y>m) return 0;
    return 1;
}
bool can(pr p){
    return can(p.first,p.second);
}
int mdis(int x,int y){
    return abs(x-n)+abs(y-m);
}
int mdis(pr p){
    return mdis(p.first,p.second);
}
int geth(pr p){
    return p.first+p.second;
}

void find0(int x,int y){
        if (vis[x][y]||!can(x,y)) return;
        vis[x][y]=1;
        if (g[x][y]) return;
        f[x][y]=1;
        if (x+y>X0+Y0)
        {
            X0=x;Y0=y;
        }
        for(int i=0;i<4;i++) find0(x+dir[i][0],y+dir[i][1]);
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {

        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            for(int j=1;j<=m;j++)
            {
                if (str[j]=='1') g[i][j]=1;
                else g[i][j]=0;
            }
        }

        X0=0;Y0=0;
        memset(vis[0],0,maxn*maxm*sizeof(vis[0][0]));
        memset(f[0],0,maxn*maxm*sizeof(f[0][0]));
        find0(1,1);
        //cout<<X0<<' '<<Y0<<endl;
        if (X0+Y0==n+m){
            printf("%d\n",0);
            continue;
        }
        if (X0+Y0<2)
        {
            X0=1;Y0=1;
            f[1][1]=1;
            printf("1");
        }
        for(int i=X0+Y0;i<n+m;i++)
        {
            int k=1;
            for(int j=max(1,i-m);j<=min(n,i-1);j++)
                if (f[j][i-j])
            {
                int k1=j<n?g[j+1][i-j]:1;
                int k2=i-j<m?g[j][i-j+1]:1;
                k=min(k,min(k1,k2));
            }
            for(int j=max(1,i-m);j<=min(n,i-1);j++)
                if (f[j][i-j])
            {
                int k1=j<n?g[j+1][i-j]:1;
                int k2=i-j<m?g[j][i-j+1]:1;
                if (k1==k) f[j+1][i-j]=1;
                if (k2==k) f[j][i-j+1]=1;
            }
            printf("%d",k);
        }
        puts("");
    }
    return 0;
}
Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview1
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python10
RMQ1
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×